Home » Data Structure

Find the maximum AND value of a pair in an array of N integers

Here is the program to find the maximum AND value of a pair in an array of N integers in C:

C program to find the maximum AND value of a pair in an array of N integers

#include <stdio.h>

// Function to check if there exists at least two elements
// in array with given bit set
int countPairsWithBitSet(int arr[], int n, int pattern) {
  int count = 0;
  for (int i = 0; i < n; i++) {
    if ((arr[i] & pattern) == pattern) {
      count++;
    }
  }
  return count;
}

// Function to return the maximum AND value of any pair in array
int maxAND(int arr[], int n) {
  int result = 0;
  int count;

  // Iterate over all bits from most significant
  // bit to least significant bit
  for (int bit = 31; bit >= 0; bit--) {
    // Find the pattern we get by setting
    // the current bit in the result
    int pattern = result | (1 << bit);

    // Check the count of pairs with this bit set
    count = countPairsWithBitSet(arr, n, pattern);

    // If there are at least two pairs
    // set the current bit in the result
    if (count >= 2) {
      result = pattern;
    }
  }
  return result;
}

int main() {
  int arr[] = {40, 80, 60, 20};
  int n = sizeof(arr) / sizeof(arr[0]);

  printf("The maximum AND value of a pair in the array is: %d\n",
         maxAND(arr, n));

  return 0;
}

Output

The maximum AND value of a pair in the array is: 40