Maximum XOR of two numbers in an array
HardGreedily take the opposite bit at every level
Problem
Given an array of integers, find the maximum XOR of any two numbers in it.
Build a bit-trie of the numbers; for each, greedily walk toward opposite bits to maximise the XOR.
The idea
Insert every number into a binary trie, then for each number walk down preferring the opposite bit at each step, because a 1 in a higher position outweighs everything below it. That greedy descent finds the best partner in O(32) per number instead of trying all pairs.
The trick
- Opposite bit gives a 1 in the XOR — always worth more than anything lower.
- Fall back to the same bit when the opposite branch is missing.
- O(n · 32) overall, versus O(n²) for the brute-force pairing.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [3,10,5,25,2,8] Values: 3, 10, 5, 25, 2, 8.
1insert all numbers into a binary trie2for each x: walk trie preferring the opposite bit, build best XOR3return maxInput
- array
- [3, 10, 5, 25, 2, 8]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [3, 10, 5, 25, 2, 8]
- Output:
- 28
- Explanation:
- 5 XOR 25 = 28 is the biggest.
Example 2
- Input:
- nums = [0]
- Output:
- 0
- Explanation:
- Only one number → 0.
Example 3
- Input:
- nums = [2, 4]
- Output:
- 6
- Explanation:
- 2 XOR 4 = 6.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.