Given a very large array of integers in which element can go upto 10^9 how do I find a pair with maximum AND value. My current approach is I calculate all possible pairs and traverse through it and find maximum, however it is very slow. Any other approach?
As long as you can find at least two numbers with the same most significant bit set, the solution will involve two of them.
Next, discard all other elements and remove everything left of this MSB for the numbers not discarded and solve the same problem. Until you have just two numbers remaining or there is nothing left to do.
For example:
input || first iteration | second iteration
=================================================================
1110010 || x | x
0110111 || discarded | discarded
1000000 || x | discarded
1000010 || x | x
=================================================================
=> solution: first and last
This is O(n log max_element).