Maximum XOR of Two Numbers in an Array

Problem

Fingerprint matching systems score two records by how many feature bits differ - the more bits differ, the more distinguishable the pair. Given an array of non-negative integers, pick any two different elements (indices differ; values may match) and return the maximum XOR value they can produce.

Example 1:

Input: nums = [6, 11, 9, 4]
Output: 15
Explanation: 11 XOR 4 = 0b1011 XOR 0b0100 = 0b1111 = 15; no other pair XORs higher.

Example 2:

Input: nums = [13, 22, 7, 1]
Output: 27
Explanation: 13 XOR 22 = 0b01101 XOR 0b10110 = 0b11011 = 27.

Example 3:

Input: nums = [8, 8, 8]
Output: 0
Explanation: every pair XORs to 0 - identical values cancel in all bit positions.

Constraints:

• 2 <= nums.length <= 2 * 10^4
• 0 <= nums[i] <= 2^31 - 1

Solution Breakdown

Approach - greedy per-bit construction with a prefix hash set.

XOR is decided independently at every bit position, and a higher bit outweighs all lower bits combined - so the answer can be built greedily from bit 31 downward. At each step, mask covers every bit at or above the current one, and prefixes holds each number's value cut down to those bits: exactly the bits the answer has decided so far (or is deciding now). The question for the current bit is "can the answer keep this bit set on top of the bits it already has?" - formalized as candidate = best | (1 << bit). That candidate is achievable if and only if some two prefixes XOR to it.

The pair search needs no double loop, because XOR is its own inverse: p ^ q == candidate rearranges to q == p ^ candidate. So for each prefix p, the required partner is fully determined, and checking "does some pair exist" becomes n hash-set membership tests. If any passes, best keeps the bit; if none, the bit is dropped and the loop moves down with best unchanged. The check is exact rather than hopeful - the prefixes contain precisely the decided bits, so passing the test means a real pair of numbers achieves candidate, and failing it means none can. Trace [6, 11, 9, 4]: at bit 3 the prefixes (masked to the top nibble) are {0, 16} and candidate 8 finds no partner; at bit 2 the set is {0, 12, 8, 4} and candidate 12 succeeds (4 ^ 8), then bit 1 and bit 0 both succeed - best ends at 15, produced by 11 ^ 4.

Edge cases - identical values like [8, 8, 8] never pass a candidate test (every prefix is the same, forcing candidate = 0), so the result is 0; a single element can only pair with itself, also 0; duplicated values are deduplicated by the set for free.

Complexity - O(32 n) time, which is O(n) for bounded-width integers: 32 rounds, each building and probing an n-element set in linear time; O(n) space for the per-round set. The binary-trie variant has the same asymptotics - the prefix set is that trie flattened into a hash lookup.