244. Maximum XOR of Two Numbers in an Array

Build the answer from the most significant bit down. At each bit, optimistically assume we can set it, then check whether two number-prefixes actually XOR to the target so far.

Greedy on bits

Process bits from bit 31 down to 0. Maintain a mask of the bits considered so far and the best maxXor. At each bit, tentatively try to set it (candidate = maxXor | (1<<i)) and gather all number prefixes num & mask into a set. If some prefix p has candidate ^ p also in the set, then two numbers can achieve candidate — keep it.

for i from 31 down to 0:
    mask |= 1<<i
    prefixes = {num & mask}
    candidate = maxXor | (1<<i)
    if any (candidate ^ p) in prefixes: maxXor = candidate

(Equivalent to walking a binary trie greedily.)

Worked example

[3,10,5,25,2,8] → 5 XOR 25 = 28, the maximum.

Complexity

• Time: O(32 · n).
• Space: O(n).

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findMaximumXOR(int[] nums) {
        int maxXor = 0, mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i);
            Set<Integer> prefixes = new HashSet<>();
            for (int num : nums) prefixes.add(num & mask);
            int candidate = maxXor | (1 << i);
            for (int p : prefixes) {
                if (prefixes.contains(candidate ^ p)) {
                    maxXor = candidate;
                    break;
                }
            }
        }
        return maxXor;
    }
}