Do you think IIT Guwahati certified course can help you in your career?
Introduction:
We are given an array of ‘N’ integers. We need to find the maximum Bitwise AND value of any pair in the array.
Let us see a few examples.
Input 1: [1, 2, 3, 4, 5]
Output 1: 4
Explanation 1: The maximum bitwise AND value is of the pair (4, 5) i.e. 4.
4 -> 1 0 0
5 -> 1 0 1
Only 3rd bit from left is common.
Input 2: [15, 6, 3, 1, 5]
Output 2: 6
Explanation 2: The maximum bitwise AND value is of the pair (6, 15) i.e. 6.
6 -> 0 1 1 0
15 -> 1 1 1 1
Only 2nd and 3rd bits from left are common.
Approach 1:
Step 1. First, initialize a variable “maxAnd” with zero.
Step 2. Create two nested for loops to find the AND of all possible pairs and keep updating the “maxAnd” variable with the maximum bitwise AND value obtained while running the loops.
Step 3. Return the “maxAnd” obtained after the completion of the running of the loops which will contain the Maximum bitwise AND value.
class Solution{
public static int maxAND (int a[], int n) {
int maxAnd = 0;
for(int i = 0;i < n;i++){
for(int j = i + 1;j < n;j++){
maxAnd = Math.max(maxAnd , (a[i] & a[j]));
}
}
return maxAnd ;
}
}
You can also try this code with Online Java Compiler
Time Complexity: The time complexity for the above approach is O(N * N) (where N is the number of elements in the array). We are running two nested for loops of O(N) time.
Space Complexity: The space complexity for the above approach is O(1) because we are not using any auxiliary space.
Approach 2:
As we know there are 32 bits in the integer. We can iterate all the bits from the left side i.e. Most significant bit and check if more than one element contains that bit or not. Also, we need to check if the bits which we have included earlier should also be present in those numbers.
Let us see this with an example.
Let us say the given Array is [1, 2, 3, 4, 5]
Their binary representation are:-
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
We will start from the leftmost bit i.e. the third bit.
Since two of the numbers have the third bit set to 1 we will include this bit to our result.
Now we will move to the second bit.
Here we have two elements with the second bit set to 1 but none of the elements has the third bit which we included earlier set to one. Hence, we will not include this bit to our result.
Now we will move to the first bit.
Here we have three elements with the first bit set to 1 but only one of the elements has the third bit which we included earlier is set to one. Hence, we will not include this bit in our result.
Hence our final result will have only the third bit set to 1. So our answer is 4 for this input array.
class Solution{
static int maxAND (int arr[], int n){
int res = 0;
/*
We will iterate all the
32 bits starting from
the leftmost bit
*/
for (int bit = 31; bit >= 0; bit--)
{
// find the count of element
// having set msb
int count = 0, cVal = (res | (1<<bit));
/*
Counting the number of elements
with the ith bit and the already
included bits set to 1.
*/
for (int i = 0; i < n; i++){
if ((cVal & arr[i]) == cVal){
count++;
}
}
/*
If the count >= 2 we will
include the current bit to
our result.
*/
if ( count >= 2 ) {
res |= (1 << bit);
}
}
return res;
}
}
You can also try this code with Online Java Compiler
Time Complexity: The time complexity for the above approach is O(N * log(M)) (where N is the total number of elements in the array and M is the largest element in the array). We are running two nested for loops of O(log(M)) and O(N) time.
Space Complexity: The space complexity for the above approach is O(1) because we are not using any auxiliary space.
What is the most optimized approach to solve the Maximum bitwise AND value of a pair in an array? The most optimized approach is based on the idea that there are 32 bits in the integer. We can iterate all the bits from the left side i.e. Most significant bit and check if more than one element contains that bit or not. Also, we need to check if the bits which we have included earlier should also be present in those numbers.
What is the time complexity for the most optimized approach of the Maximum bitwise AND value of a pair in an array question? The time complexity for the most optimized approach is O(N * log(M)) (where N is the total number of elements in array and M is the largest element in the array). We are running two nested for loops of O(log(M)) and O(N) time.
Key Takeaways:
In this blog, we have covered the following things:
We first discussed the brute force approach to solve the Maximum bitwise AND value of a pair in an array.
Then we discussed the most optimized approach to solve the Maximum bitwise AND value of a pair in an array question.
If you want to learn more about Bit Manipulation and want to practice some questions which require you to take your basic knowledge on Bit Manipulations a notch higher, then you can visit our Guided Path for Bit Manipulation.
34+ registered 
