Maximum Bitwise AND

Hard
0/120
profile
Contributed by
1 upvote
Asked in company
Deloitte

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
6
2 5 5 8 5 1
2
2 4
Sample Output 1 :
5
0
Explanation For Sample Input 1 :
For test case 1 :
We will print 5 because:
We can select ARR[1], ARR[2] and ARR[4] and we will 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 two or more integers from the array.

For test case 2 : 
We will print 0 because:
There are two integers in the array, we need to select at least two integers, therefore we will have to select both the integers in the array, ARR[0] & ARR[1] = (2 & 4) = 0. Hence we will print 0.
Sample Input 2 :
2
5
2 4 8 16 32
6
2 4 8 16 32 20
Sample Output 2 :
0
16
Hint

Bitwise AND of two numbers is always smaller than equal to both the numbers, therefore the optimal answer will exist by selecting exactly two numbers from the array. Try to consider each pair one by one.

Approaches (2)
Brute Force

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 :

  1. Initialize ‘ans’ equal to 0, this variable stores the maximum bitwise AND.
  2. 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.
  3. Finally, return the value of ‘ans’.
Time Complexity

O( N ^ 2 ), where N denotes the size of the array.

 

We check the bitwise AND of each possible pair, there are a total of N^2 pairs possible.

Hence the time complexity is O( N^2 ).

Space Complexity

O( 1 )

 

No auxiliary space is used.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Maximum Bitwise AND
Full screen
Console