Given a list of positive integers, find the largest possible value of $a[i]$ $\&$ $a[j]$, where $i$, $j$ are indices of the list. $ i\ne j $, $a[i]\,\&\,a[j]$ is bitwise AND of $a[i]$ and $a[j]$.
I need to find a linearithmic or linear time algorithm to solve the problem.
I think, I need to choose one number such that it's highest one bit is maximum, in the list of numbers, and then, the other number should have zeroes where the first one has ones, and vice-versa.
However, I am unable to frame a proper algorithm from the above idea.
Log time is clearly not possible in an unsorted array, but here is an O(n k) time algo where k is number of bits the numbers can have:
Assume integers are given in binary representation.
Set 'prefix' to empty.
for i from 1 to k: { Count = number of integers in the list which start with prefix followed by 1.
If count is at least 2 then append 1 to prefix else append 0 to it }
At the end, interpret prefix as a k bit integer m. Then the maximum and is m. We can do some extra bookkeeping to find the elements which got to m (store any two elements from last set which led to updating of count)