Two elements in array whose xor is maximum

Question

Given an array of integers ,You have to find two elements whose XOR is maximum.

There is naive approach --just by picking each element and xoring with other elements and then comparing the results to find the pair.

Other than this ,Is there any efficient algorithm?

Answer 1

I think I have an O(n lg U) algorithm for this, where U is the largest number. The idea is similar to user949300's, but with a bit more detail.

The intuition is as follows. When you're XORing two numbers together, to get the maximum value, you want to have a 1 at the highest possible position, and then of the pairings that have a 1 at this position, you want a pairing with a 1 at the next possible highest position, etc.

So the algorithm is as follows. Begin by finding the highest 1 bit anywhere in the numbers (you can do this in time O(n lg U) by doing O(lg U) work per each of the n numbers). Now, split the array into two pieces - one of the numbers that have a 1 in that bit and the group with 0 in that bit. Any optimal solution must combine a number with a 1 in the first spot with a number with a 0 in that spot, since that would put a 1 bit as high as possible. Any other pairing has a 0 there.

Now, recursively, we want to find the pairing of numbers from the 1 and 0 group that has the highest 1 in them. To do this, of these two groups, split them into four groups:

• Numbers starting with 11
• Numbers starting with 10
• Numbers starting with 01
• Numbers starting with 00

If there are any numbers in the 11 and 00 group or in the 10 and 01 groups, their XOR would be ideal (starting with 11). Consequently, if either of those pairs of groups isn't empty, recursively compute the ideal solution from those groups, then return the maximum of those subproblem solutions. Otherwise, if both groups are empty, this means that all the numbers must have the same digit in their second position. Consequently, the optimal XOR of a number starting with 1 and a number starting with 0 will end up having the next second bit cancel out, so we should just look at the third bit.

This gives the following recursive algorithm that, starting with the two groups of numbers partitioned by their MSB, gives the answer:

• Given group 1 and group 0 and a bit index i:
  • If the bit index is equal to the number of bits, return the XOR of the (unique) number in the 1 group and the (unique) number in the 0 group.
  • Construct groups 11, 10, 01, and 00 from those groups.
  • If group 11 and group 00 are nonempty, recursively find the maximum XOR of those two groups starting at bit i + 1.
  • If group 10 and group 01 are nonempty, recursively find the maximum XOR of those two groups, starting at bit i + 1.
  • If either of the above pairings was possible, then return the maximum pair found by the recursion.
  • Otherwise, all of the numbers must have the same bit in position i, so return the maximum pair found by looking at bit i + 1 on groups 1 and 0.

To start off the algorithm, you can actually just partition the numbers from the initial group into two groups - numbers with MSB 1 and numbers with MSB 0. You then fire off a recursive call to the above algorithm with the two groups of numbers.

As an example, consider the numbers 5 1 4 3 0 2. These have representations

101  001  100   011   000   010

We begin by splitting them into the 1 group and the 0 group:

101  100
001  011  000  010

Now, we apply the above algorithm. We split this into groups 11, 10, 01, and 00:

11:
10:  101  100
01:  011  010
00:  000  001

Now, we can't pair any 11 elements with 00 elements, so we just recurse on the 10 and 01 groups. This means we construct the 100, 101, 010, and 011 groups:

101: 101
100: 100
011: 011
010: 010

Now that we're down to buckets with just one element in them, we can just check the pairs 101 and 010 (which gives 111) and 100 and 011 (which gives 111). Either option works here, so we get that the optimal answer is 7.

Let's think about the running time of this algorithm. Notice that the maximum recursion depth is O(lg U), since there are only O(log U) bits in the numbers. At each level in the tree, each number appears in exactly one recursive call, and each of the recursive calls does work proportional to the total number of numbers in the 0 and 1 groups, because we need to distribute them by their bits. Consequently, there are O(log U) levels in the recursion tree, and each level does O(n) work, giving a total work of O(n log U).

Hope this helps! This was an awesome problem!