Problem link : contest practice
Difficulty : Simple
Pre-requisites : Basic Math, Recursion, Bit Operations
Problem : Given an array find maximum AND(&) possible between any two elements.
Explanation
At first, let’s consider some partial solutions.
How to get 50 points
Here you can go through each possible pair and check what AND value is. And we can find what is the maximum AND possible. Complexity of this will be O(N*N).
n=input()
arr=[]
ans=-1
for i=1 to n:
arr[i]=input()
for i=1 to n:
for j=i+1 to n:
ans = max( ans, arr[i]&arr[j] )
How to get 100 points
When we are ANDing two numbers, we would like to have a 1 at the most significant bit(MSB). So, first we’ll try to get a 1 at MSB. Now, suppose we denote A[i]=b_in,b_in-1…b_i0, where b_i’s are the bits that could be 1 or 0.
Let’s say S be the set of A[i] whose b_in is 1 and S’ be the set of A[i] whose b_in is 0. If size of S ≥ 2 we are sure that our answer will be maximum if we chose a pair of numbers from S, because n’th bit of their AND will be 1 for sure. So, we know our answer lies in S.
However, if size of S is less than 2, we can never have n’th bit 1 in our answer. So, we’ll have to continue with n’th bit as 0. Note that our answer will now be in S’.
Now, we know our answer is in S or S’ and we also know n’th bit of our answer. So, our new subproblem is to find (n-1)‘th bit of our answer using numbers in S or S’. We can write a recursive code for this.
What will be the complexity? For each of the n bits, we’ll traverse whole array to sort according to their bits. So O(n*N). We will be keeping n=30, because A[i] ≤ 109.
n=input()
arr=[]
flag[n]={}
for i=0 to n-1:
arr[i]=input()
print foo(30)
def foo(level): //this function will find the level'th bit
//and accordingly return answer
if level==-1: // we already have solved for all bits. return 0 from here
return 0
Scount=0 // stores the size of set S
ans=0 // the answer in decimal form
for i=0 to n-1:
if flag[i]==0: // flag[i]=0 means arr[i] is available for us to use
if (arr[i]&(1<<level)): // level'th bit of arr[i] is 1
Scount++
if Scount>=2: // our answer's level'th bit will be 1
ans += (1<<level)
// but we also have to set the flag of unavailable numbers
for i=0 to n-1:
if (arr[i]&(1<<level))==0: // level'th bit is 0, set the flag
flag[i]=1
return ans+foo(level-1); // return the current answer + answer for the next bit
, I can’t still understand the idea. I mean let’s say current bit is 0 , and this node has both left and right child. So why should we go to left ? I mean the right child also may produce the maximum ans can’t it.