Theo bài toán, chúng ta được cho một mảng gồm n số nguyên dương, chúng ta phải tìm một cặp có giá trị AND lớn nhất từ mảng.
Ví dụ
Input: arr[] = { 4, 8, 12, 16 }
Output: pair = 8 12
The maximum and value= 8
Input:arr[] = { 4, 8, 16, 2 }
Output: pair = No possible AND
The maximum and value = 0 Để tìm giá trị AND tối đa tương tự như tìm giá trị AND tối đa trong một mảng. Chương trình phải tìm ra cặp phần tử tạo ra giá trị AND thu được. Để tìm các phần tử, chỉ cần duyệt qua toàn bộ mảng và tìm giá trị AND của mỗi phần tử với giá trị AND lớn nhất thu được (kết quả) và nếu arr [i] &result ==result, điều đó có nghĩa là arr [i] là phần tử sẽ tạo giá trị AND lớn nhất. Ngoài ra, trong trường hợp nếu giá trị AND lớn nhất (kết quả) bằng 0 thì chúng ta nên in "Không thể" trong trường hợp đó.
Thuật toán
int checkBit(int pattern, int arr[], int n) START STEP 1: DECLARE AND INITIALIZE count AS 0 STEP 2: LOOP FOR i = 0 AND i < n AND i++ IF (pattern & arr[i]) == pattern THEN, INCREMENT count BY 1 STEP 3: RETURN count STOP int maxAND(int arr[], int n) START STEP 1: DECLARE AND INITIALIZE res = 0 AND count STEP 2: LOOP FOR bit = 31 AND bit >= 0 AND bit-- count = GOTO FUNCTION checkBit(res | (1 << bit), arr,n) IF count >= 2 THEN, res |= (1 << bit); END IF IF res == 0 PRINT "no possible AND” ELSE PRINT "Pair with maximum AND= " count = 0; LOOP FOR int i = 0 AND i < n && count < 2 AND i++ IF (arr[i] & res) == res THEN, INCREMENT count BY 1 PRINT arr[i] END IF END FOR END FOR RETURN res STOP
Ví dụ
#include <stdio.h>
int checkBit(int pattern, int arr[], int n){
int count = 0;
for (int i = 0; i < n; i++)
if ((pattern & arr[i]) == pattern)
count++;
return count;
}
// Function for finding maximum AND value pair
int maxAND(int arr[], int n){
int res = 0, count;
for (int bit = 31; bit >= 0; bit--) {
count = checkBit(res | (1 << bit), arr, n);
if (count >= 2)
res |= (1 << bit);
}
if (res == 0) //if there is no pair available
printf("no possible and\n");
else { //Printing the pair available
printf("Pair with maximum AND= ");
count = 0;
for (int i = 0; i < n && count < 2; i++) {
// incremnent count value after
// printing element
if ((arr[i] & res) == res) {
count++;
printf("%d ", arr[i]);
}
}
}
return res;
}
int main(int argc, char const *argv[]){
int arr[] = {5, 6, 2, 8, 9, 12};
int n = sizeof(arr)/sizeof(arr[0]);
int ma = maxAND(arr, n);
printf("\nThe maximum AND value= %d ", ma);
return 0;
} Đầu ra
Nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau -
pair = 8 9 The maximum and value= 8