Description,
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

O(n) time complexity solution

Algorithm:

  1. Starting from the most significant bit(MSB) by mask, if any two number differ in this bit, we can be sure that
    this “1” will be in the result. we set the masked result to MAX.
  2. Move to the 2nd MSB, if any two number differ in this bit AND the masked number is greater than MAX, we can be sure that
    this “1” will be in the result. we set the masked result to MAX.
  3. repeat the steps.
public class Solution {
    public int findMaximumXOR(int[] nums) {
        int maxXOR = 0;
        int mask = 0;
        for (int i=31; i>=0; i--) {
            // use mask to find all MSBs at current bit position(from 32 to 1),
            // if any two MSBs differ, the MSB of result is set.
            mask = mask | (1 << i);
            // for each position, the possibleMax can be derived from
            // previous maxXOR.
            int possibleMax = maxXOR | (1 << i);
            Set<Integer> maskedNums = new HashSet<>();
            for (int num : nums) {
               maskedNums.add(num & mask); 
            }
            
            for (int candidate : maskedNums) {
                // if any two candidates have current MSBs differ,
                // we update the maxXOR
                if (maskedNums.contains(possibleMax ^ candidate)) maxXOR = possibleMax;
            }
            
            
        }
        return maxXOR;
    }
}

imgRuntime: 133ms