#421
Maximum XOR of Two Numbers in an Array
Medium Binary trie
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the maximum value of nums[i] XOR nums[j] over all pairs.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the biggest XOR of any two numbers.
Why this works: store numbers bit by bit from the top. For each number, try to go the opposite way at every bit; a 1 in a high bit beats anything lower.
Example: [3, 10, 5, 25, 2, 8]
5 (00101) with 25 (11001) → 11100 = 28✦Hints open one at a time
Store numbers bit by bit (from bit 30 down to 0) in a trie with two children per node.
To maximise XOR with x, at each bit prefer the child with the opposite bit.
↗Approach
Insert each number, and before or after inserting, walk the trie greedily choosing the opposite bit when it exists; accumulate the XOR bits. Track the best.
</>Solution (Java)
class Solution {
private static class Node {
Node[] child = new Node[2];
}
public int findMaximumXOR(int[] nums) {
Node root = new Node();
int best = 0;
for (int x : nums) {
Node ins = root, q = root;
int xor = 0;
for (int b = 30; b >= 0; b--) {
int bit = (x >> b) & 1;
if (ins.child[bit] == null) ins.child[bit] = new Node();
ins = ins.child[bit];
if (q.child[1 - bit] != null) { // opposite bit gives a 1 here
xor |= 1 << b;
q = q.child[1 - bit];
} else {
q = q.child[bit];
}
}
best = Math.max(best, xor);
}
return best;
}
}!Common mistake
Walking from the lowest bit up — the highest bits matter most, so go from the top.
Complexity
- Time: O(n · 31).
- Space: O(n · 31).
Topic: Trie
🎬 Episode 97: video coming soon