Size of the smallest subset with maximum Bitwise OR

https://www.geeksforgeeks.org/size-of-the-smallest-subset-with-maximum-bitwise-or/

Given an array of positive integers. The task is to find the size of the smallest subset such that the Bitwise OR of that set is Maximum possible.

Input : arr[] = {5, 1, 3, 4, 2}
Output : 2
7 is the maximum value possible of OR, 
5|2 = 7 and 5|3 = 7

Input : arr[] = {2, 6, 2, 8, 4, 5}
Output : 3
15 is the maximum value of OR and set
elements are 8, 6, 5

Approach : The idea is to observe that, a bit in the result of bitwise OR will be set if it is set in either of the operands. So, to maximize the value of the Bitwise OR:

• We will sort the array in decreasing order.
• Now, take the max element of the array as the maximum value of OR initially.
• Now, traverse the array and for each element calculate its Bitwise OR with maxOR so far. If it is greater than maxOR so far then increment count.

// Function to find the size of the smallest

// subset with the maximum value of Bitwise OR

int findMaxOR(int arr[], int n)

{

    // sort the array in decreasing

    // order

    sort(arr, arr + n, compare);

  

    // Maximum element in the set

    int maxOR = arr[0];

  

    int count = 1;

  

    for (int i = 1; i < n; i++) {

        // if bitwise or with the next element is

        // greater than current value

        if ((maxOR | arr[i]) > maxOR)

        // then add this element in the set and

        // update the current maxOR value

        {

            maxOR = maxOR | arr[i];

            count++;

        }

    }

  

    return count;

}