Maximum XOR of Two Numbers in an Array

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.

I follow the solution on Leetcode discuss. Basically, from highest to lowest, for each bit, we try to narrow down numbers that with XOR operations, will give this bit 1. In the first iteration, we will have all numbers that have the highest bit as 1. Then we go through the set, for each number in the set, we want to see if we can find a number in this set that by XOR it will give us 1 in the highest bit. If we can find one, we know the highest bit is the current bit we have. And we keep looking for the next bit.

public int findMaximumXOR(int[] nums) {
        int mask = 0, max = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i);
            Set prefixes = new HashSet<>();
            for (int n : nums) {
                prefixes.add(mask & n);
            }
            int tmp = max | (1 << i);
            for (int pre : prefixes) {
                if (prefixes.contains(tmp ^ pre)) {
                    max = tmp;
                    break;
                }
            }
        }
        return max;
    }