Last Updated: 11 Nov, 2021
Maximum Bitwise AND
Hard
Asked in company
Ninja is bored during his algorithm class and wants to play with numbers. He then starts quizzing people about this topic. It's your turn now!
You are given an array containing ‘N’ integers. You have to select more than one number from this array and calculate their bitwise AND, find the maximum value of bitwise AND that you can get.
For Example :
If 'N' = 6, 'ARR' = {2, 5, 5, 8, 5, 1}
You can select 'ARR[1]', 'ARR[2]' and 'ARR[4]' and you can get 'ARR[1]' & 'ARR[2]' & 'ARR[4]' = 5 & 5 & 5 = 5 as the maximum bitwise AND.
It’s not possible to get bitwise AND greater than 5 by selecting more than one integers from the array.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’, denoting the number of elements in the array.
The second line of each test case contains 'N' integers ‘ARR’, denoting the array elements.
Output Format :
For each test case, print the maximum value of bitwise AND that you can get.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ 'T' ≤ 10
2 ≤ 'N' ≤ 1000
0 ≤ 'ARR[i]' ≤ 10^9
Time limit: 1 sec
Approaches
Bitwise AND of two numbers is always less than or equal to both the numbers, therefore we can easily see that once we have calculated the bitwise AND of two numbers from the array, then selecting the third number won’t increase our final answer. Hence, check the bitwise AND of all the pairwise numbers and output the maximum value.
The steps are as follows :
- Initialize ‘ans’ equal to 0, this variable stores the maximum bitwise AND.
- Run an outer FOR loop for variable ‘i’ from 0 to N - 1, and run an inner FOR loop for variable ‘j’ from i + 1 to N - 1. Each time calculate the value of ARR[i] & ARR[j] (where ‘&’ denotes bitwise AND operator), also update ‘ans’ if needed.
- Finally, return the value of ‘ans’.
It’s sufficient to select two numbers from the array to get the optimal answer, refer to Approach-1 if you need a detailed explanation for this.
A general and basic way to solve problems involving bitwise operations is to think in terms of bits, here also it is easy to figure out that it’s sufficient to figure out which bits will contribute to our final answer. Also, note that we will greedily select MSB first if possible, this is because (2 + 22 + 23 + 2i-1) < 2i, therefore if it is possible we will select the ith bit in our final answer and then check for the i-1th bit.
We start from the 31st bit as ‘ARR[i]’ ≤ 109. For the current bit, we will calculate the count of numbers that have the current bit is ON. If the count is greater than 1 then we may include the ith bit in our answer. But note that this is not a sufficient condition as we also need to take into consideration the bits that we have previously selected in answer should also be ON in the current number to be included in the count. Once we have checked this condition for the 0th bit we can return the final answer calculated.
The steps are as follows :
- Initialize ‘ans’ equal to 0, this variable stores the maximum bitwise AND.
- Run an outer FOR loop for variable ‘bit’ from 31 to 0.
- Initialize a variable ‘count’ equal to 0.
- Run an inner FOR loop for variable ‘i’ from 0 to N - 1.
- If the current bit of ARR[i] is ON and also if bitwise AND of ‘ARR[i]’ and ‘ans’ is equal to ‘ans’ then increment the value of ‘count’ by one.
- Check if ‘count’ is greater than or equal to two, if so then increment the value of ‘ans’ by 2bit as the current bit will contribute to our final answer.
- Finally, return the value of ‘ans’.
Similar problems