Minimize replacements of Array elements to make bitwise AND greater than K
Given an array A[] of N integers and an integer K, the task is to find the minimum number of replacements of array elements required such that the bitwise AND of all array elements is strictly greater than K.
Examples:
Input: N = 4, K = 2, A[] = {3, 1, 2, 7}
Output: 2
Explanation: Change A[1] = 3 and A[2] = 11.
After performing two operations: Modified array: {3, 3, 11, 7}
Now, Bitwise AND of all the elements is 3 & 3 & 11 & 7 = 3Input: N = 3, K = 1, A[] = {2, 2, 2}
Output: 0
Approach: This problem can be solved using Bit Manipulation as per the following idea:
Find the bit representation of the value K. For each bit assume that is set and calculate how many replacements are required to achieve that value as bitwise AND of array elements. The minimum among these values is the required answer.
Follow the below steps to implement the above observation:
- Create a mask variable with 32 bit and initialize it to zero.
- Starting from the 31st most significant bit keep checking if the ith bit in K is set or not.
- If the ith bit is set then set that bit in the mask also.
- If the bit is not set then create a temporary variable (say temp) having the value of mask but having the ith bit set so that bitwise AND of the array can be strictly greater than K.
- For each element in the array check if the bitwise AND of the element and temp is equal to temp.
- If it is temp then there is no need to change this element of the array.
- Find the number of replacements (say X) by subtracting the count of elements not requiring change from N (the size of the array).
- The minimum value of X among all iterations from all 31st bit to 0th bit is the answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the // minimum number of replacements int count( int N, vector< int > A, int K) { // Initially assuming we need to change // all elements of the array int ans = N; // Initialize mask as 0 int mask = 0; // Starting from 31st bit check all // the bits of X if they are set or not for ( int i = 31; i >= 0; i--) { // If bit is set, // set that bit in mask also if ((K >> i) & 1) mask |= (1 << i); // If bit is not set then // count the elements of array // requiring no change // and change answer to // minimum replacements. else { int good = 0; int temp = mask | (1 << i); for ( auto element : A) if ((element & temp) == temp) good++; ans = min(ans, N - good); } } return ans; } // Driver code int main() { int N = 4, K = 2; vector< int > A = { 3, 1, 2, 7 }; // Function call int ans = count(N, A, K); cout << ans << endl; return 0; } |
C
// C code to implement the approach #include<stdio.h> #include<math.h> int min( int a, int b) { return a<b?a:b; } // Function to find the minimum number of replacements int count( int N, int A[], int K) { // Initially assuming we need to change all elements of the array int ans = N; // Initialize mask as 0 int mask = 0; // Starting from 31st bit check all the bits of X if they are set or not for ( int i = 31; i >= 0; i--) { // If bit is set, set that bit in mask also if ((K >> i) & 1) mask |= (1 << i); // If bit is not set then count the elements of array requiring no change and change answer to minimum replacements. else { int good = 0; int temp = mask | (1 << i); for ( int i=0;i<N;i++) if ((A[i] & temp) == temp) good++; ans = min(ans, N - good); } } return ans; } // Driver code int main() { int N = 4, K = 2; int A[] = {3,1,2,7}; // Function call int ans = count(N, A, K); printf ( "Ans : %d" ,ans); return 0; } //This code is contributed by ashishsingh13122000 |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to find the // minimum number of replacements static int count( int N, int [] A, int K) { // Initially assuming we need to change // all elements of the array int ans = N; // Initialize mask as 0 int mask = 0 ; // Starting from 31st bit check all // the bits of X if they are set or not for ( int i = 31 ; i >= 0 ; i--) { // If bit is set, // set that bit in mask also if (((K >> i) & 1 ) != 0 ) mask |= ( 1 << i); // If bit is not set then // count the elements of array // requiring no change // and change answer to // minimum replacements. else { int good = 0 ; int temp = mask | ( 1 << i); for ( int element : A) if ((element & temp) == temp) good++; ans = Math.min(ans, N - good); } } return ans; } // Driver code public static void main (String[] args) { int N = 4 , K = 2 ; int A[] = { 3 , 1 , 2 , 7 }; // Function call int ans = count(N, A, K); System.out.println(ans); } } // This code is contributed by hrithikgarg03188. |
Python
# Python code to implement the approach # Function to find the # minimum number of replacements def count(N, A, K): # Initially assuming we need to change # all elements of the array ans = N # Initialize mask as 0 mask = 0 # Starting from 31st bit check all # the bits of X if they are set or not i = 31 while (i > = 0 ): # If bit is set, # set that bit in mask also if ((K >> i) & 1 ): mask | = ( 1 << i) # If bit is not set then # count the elements of array # requiring no change # and change answer to # minimum replacements. else : good = 0 temp = mask | ( 1 << i) for x in range ( 0 , len (A)): if ((A[x] & temp) = = temp): good + = 1 ans = min (ans, N - good) i - = 1 return ans # Driver code N = 4 K = 2 A = [ 3 , 1 , 2 , 7 ] # Function call ans = count(N, A, K) print (ans) # This code is contributed by Samim Hossain Mondal. |
C#
// C# code to implement the approach using System; class GFG { // Function to find the // minimum number of replacements static int count( int N, int [] A, int K) { // Initially assuming we need to change // all elements of the array int ans = N; // Initialize mask as 0 int mask = 0; // Starting from 31st bit check all // the bits of X if they are set or not for ( int i = 31; i >= 0; i--) { // If bit is set, // set that bit in mask also if (((K >> i) & 1) != 0) mask |= (1 << i); // If bit is not set then // count the elements of array // requiring no change // and change answer to // minimum replacements. else { int good = 0; int temp = mask | (1 << i); foreach ( int element in A) if ((element & temp) == temp) good++; ans = Math.Min(ans, N - good); } } return ans; } // Driver code public static void Main() { int N = 4, K = 2; int [] A = { 3, 1, 2, 7 }; // Function call int ans = count(N, A, K); Console.WriteLine(ans); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the // minimum number of replacements function count(N, A, K) { // Initially assuming we need to change // all elements of the array let ans = N; // Initialize mask as 0 let mask = 0; // Starting from 31st bit check all // the bits of X if they are set or not for (let i = 31; i >= 0; i--) { // If bit is set, // set that bit in mask also if ((K >> i) & 1) mask |= (1 << i); // If bit is not set then // count the elements of array // requiring no change // and change answer to // minimum replacements. else { let good = 0; let temp = mask | (1 << i); for (let element of A) if ((element & temp) == temp) good++; ans = Math.min(ans, N - good); } } return ans; } // Driver code let N = 4, K = 2; let A = [3, 1, 2, 7]; // Function call let ans = count(N, A, K); document.write(ans + '<br>' ) // This code is contributed by Potta Lokesh </script> |
Output:
2
Time Complexity: O(N * LogM) where M is the maximum element of array.
Auxiliary Space: O(1)
Contact Us