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 from 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++
// C++ program to find Minimum bitwise OR// after removing at most K elements.#include <bits/stdc++.h>using namespace std;// Function to find the minimum possible ORint minimumOR(vector<int> A, int N, int K){ vector<int> SetBitCount(32, 0); int OR = 0, FirstSetBit = 0; // Sort in reverse order sort(A.rbegin(), A.rend()); for (int i = 0; i < N; i++) { FirstSetBit = log2(A[i]) + 1; SetBitCount[FirstSetBit]++; } // Traverse from MSB to LSB 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;}// Driver codeint main(){ int N = 7; vector<int> A = { 1, 10, 9, 4, 5, 16, 8 }; int K = 3; cout << minimumOR(A, N, K); return 0;} |
Java
// Java program to find Minimum bitwise OR// after removing at most K elements.import java.util.*;public class GFG{ // Function to reverse an array static void reverse(int a[], int n) { int i, k, t; for (i = 0; i < n / 2; i++) { t = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = t; } } // Function to find the minimum possible OR static int minimumOR(int[] A, int N, int K) { int[] SetBitCount = new int[32]; for (int i = 0; i < 32; i++) { SetBitCount[i] = 0; } int OR = 0, FirstSetBit = 0; // Sort array in ascending order. Arrays.sort(A); // reverse array reverse(A, N); for (int i = 0; i < N; i++) { FirstSetBit = (int)(Math.log(A[i]) / Math.log(2)) + 1; SetBitCount[FirstSetBit]++; } // Traverse from MSB to LSB 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; } // Driver code public static void main(String args[]) { int N = 7; int[] A = { 1, 10, 9, 4, 5, 16, 8 }; int K = 3; System.out.println(minimumOR(A, N, K)); }}// This code is contributed by Samim Hossain Mondal. |
Python
# Python program to find Minimum bitwise OR# after removing at most K elements.import math# Function to find the minimum possible ORdef minimumOR(A, N, K): SetBitCount = [0] * 32 OR = 0 FirstSetBit = 0 # Sort in reverse order A.sort(reverse=True) for i in range(0, N): FirstSetBit = int(math.log(A[i], 2)) + 1 SetBitCount[FirstSetBit] += 1 # Traverse from MSB to LSB j = 0 i = 31 while(i >= 0): if (SetBitCount[i] <= K): K -= SetBitCount[i] j += SetBitCount[i] else: x = j while(j < x + SetBitCount[i]): OR = OR | A[j] j += 1 i -= 1 return OR# Driver codeN = 7A = [1, 10, 9, 4, 5, 16, 8]K = 3print(minimumOR(A, N, K))# This code is contributed by Samim Hossainn Mondal. |
C#
// C# program to find Minimum bitwise OR// after removing at most K elements.using System;class GFG { // Function to find the minimum possible OR static int minimumOR(int[] A, int N, int K) { int[] SetBitCount = new int[32]; for (int i = 0; i < 32; i++) { SetBitCount[i] = 0; } int OR = 0, FirstSetBit = 0; // Sort array in ascending order. Array.Sort(A); // reverse array Array.Reverse(A); for (int i = 0; i < N; i++) { FirstSetBit = (int)Math.Log(A[i], 2) + 1; SetBitCount[FirstSetBit]++; } // Traverse from MSB to LSB 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; } // Driver code public static void Main() { int N = 7; int[] A = { 1, 10, 9, 4, 5, 16, 8 }; int K = 3; Console.Write(minimumOR(A, N, K)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the minimum possible OR function minimumOR(A, N, K) { let SetBitCount = new Array(32).fill(0); let OR = 0, FirstSetBit = 0; // Sort in reverse order A.sort(function (a, b) { return b - a }) for (let i = 0; i < N; i++) { FirstSetBit = Math.log2(A[i]) + 1; SetBitCount[FirstSetBit]++; } // Traverse from MSB to LSB for (let i = 31, j = 0; i >= 0; i--) { if (SetBitCount[i] <= K) { K -= SetBitCount[i]; j += SetBitCount[i]; } else { for (let x = j; j < x + SetBitCount[i]; j++) OR = OR | A[j]; } } return OR; } // Driver code let N = 7; let A = [1, 10, 9, 4, 5, 16, 8] let K = 3; document.write(minimumOR(A, N, K)); // This code is contributed by Potta Lokesh </script> |
Output
11
Time Complexity: O(N* log(N))
Auxiliary Space: O(N)
Take a part in the ongoing discussion
