News Leaflets
0 99

Given an array A[] of length N, the task is to find the minimum possible value of bitwise OR of the elements after removing at most K elements.

Examples:

Input: A = {1, 10, 9, 4, 5, 16, 8}, K = 3
Output: 11
Explanation: Remove 4, 5, 16 for the given array.
The remaining elements are {1, 10, 9, 5}.
The OR of these elements are 11 which is the minimum possible.

Input: A = {1, 2, 4, 8}, K = 1
Output: 7
Explanation: Remove 8 form the Array, Minimum OR= 1 | 2 | 4 = 7

Approach: This problem can be solved using bit manipulation on the basis of the following idea:

Try to remove the highest MSB elements first, then the elements having 2nd highest MSB and so on until K elements are removed.

Follow the illustration given below for a better understanding.

Illustration :

Consider A[] = [1, 10, 9, 4, 5, 16, 8 ]

• Binary representation of the elements are:
1 – 00001
10 – 01010
9 – 01001
4 – 00100
5 – 00101
16  – 10000
8 – 01000
• The positions of the MSB of every elements are:
1 -> 0, 10 -> 3, 9 -> 3, 4 -> 2, 5 -> 2, 16  -> 4, 8 -> 3
• Therefore count of elements having MSB at ith position are as given below:
setBitCount = [1, 0, 2, 3, 1 ]
MSB position    0, 1, 2, 3, 4
• Traverse array and check if current setBitCount is less than k, then remove all elements with current Bit as FirstSetBit.
For, K = 3, traverse array:
=>When i = 4: setBitCount[i] = 1, which is less than K so remove 16, and now K = 2.
=>When i = 3: K < setBitCount[i] (i.e 3). So don’t remove it.
=>When i = 2: setBitCount[i] = 2 ≤ K, so remove 4 and 5. Now, K =0.
• Calculate OR for all remaining elements i.e (1, 5, 9, 10) = 11

Follow the steps mentioned below to implement the above observation:

• Create a hash array.
• Traverse the given array and increment the MSB Index of every element into the hash array.
• Now, traverse the hash array from MSB and in each iteration:
• Check if it is possible to remove all elements having the ith bit as MSB  i.e. setBitCount ≤ K.
• If setBitCount ≤ K, don’t calculate OR for that elements and, just decrease the K.
• if not, calculate the OR for elements with ith bit as MSB.
• Return Calculate OR after removing K elements.

Below is the implementation of the above approach:

## C++

 #include using namespace std;    int minimumOR(vector A, int N, int K) {     vector SetBitCount(32, 0);     int OR = 0, FirstSetBit = 0;             sort(A.rbegin(), A.rend());     for (int i = 0; i < N; i++) {         FirstSetBit = log2(A[i]) + 1;         SetBitCount[FirstSetBit]++;     }             for (int i = 31, j = 0; i >= 0; i--) {         if (SetBitCount[i] <= K) {             K -= SetBitCount[i];             j += SetBitCount[i];         }         else {             for (int x = j;                  j < x + SetBitCount[i]; j++)                 OR = OR | A[j];         }     }        return OR; }    int main() {     int N = 7;     vector A = { 1, 10, 9, 4, 5, 16, 8 };     int K = 3;        cout << minimumOR(A, N, K);     return 0; }

Time Complexity: O(N* log(N))
Auxiliary Space: O(N)