How to find MAX-XOR in an array?

Question

Given an array A of unsigned 32-bit ints, choose two in-bounds indices i, j so as to maximize the value of A[i] ^ A[j], where ^ is the bitwise XOR (exclusive OR) operator. If there are multiple possible answers, print any one.

Example Input:

4 2 0 13 49 

Output:

3 4 

Explanation: 13 ^ 49 is 60, 13 and 49 are positioned at indexes 3 and 4. Printing "4 3" would have been equally valid.
EDIT:- Let k be the bit width (maximum number of bits) of the primitive.
Constraint:- Only Sub-quadratic complexity. An O(k*arr.length) time.

Answer 1

I am not providing the code (sorry) just the concept -

1. XOR flips the bits so at some place you should have two numbers which has different bit value at same position.
2. Find the highest bit and divide the array into two parts such that
   a. one group has all numbers with highest bit set (one number will come from this grp)
   b. other group has all the same bit as reset. (another number will come from this grp)
3. Not we need to from the highest bit to second highest bit such that
   a. Pick from first group and divide into two parts where second highest bit is set or reset.
   b. Pick from second group and divide into two parts where second highest bit is set or reset.
   in this step you will eliminate lot of numbers where highest bit is different and second highest bit is same.

And run this algo recursively (implementation is not easy) but should give you some pointer.