346. Maximum XOR of Two Numbers in an Array
You are given an array of non-negative integers nums. Pick two positions i and j with 0 <= i <= j < nums.length (picking the same position twice is allowed) and compute nums[i] XOR nums[j].
Return the largest value this XOR can take over all choices of i and j.
A brute-force scan of every pair is quadratic. The interesting part is doing it in about 31 passes — one per bit — or with a binary trie.
Example 1:
Input: nums = [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: 5 XOR 25 = 00101 XOR 11001 = 11100 = 28, and no other pair beats it.
Example 2:
Input: nums = [14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70]
Output: 127
Explanation: The pair 36 XOR 91 fills all seven low bits: 0100100 XOR 1011011 = 1111111 = 127.
Constraints:
- 1 ≤ nums.length ≤ 2 * 10⁵
- 0 ≤ nums[i] < 2³¹
Hints:
XOR is decided bit by bit, and a high bit outweighs ALL lower bits combined: 10000 beats 01111. So the best answer is the one that wins the most-significant bit fight first.
Build the answer greedily from bit 30 down: assume the next bit of the answer can be 1, and check whether any two numbers' prefixes (their top bits) XOR to that candidate. A hash set of prefixes plus the identity a XOR b = c <=> a XOR c = b makes the check O(n).
Alternatively, insert every number into a binary trie of its bits (MSB first). To find the best partner for x, walk down the trie always trying the child with the OPPOSITE bit of x — that greedy walk maximizes the XOR.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 10, 5, 25, 2, 8]
Expected output: 28