Maximum XOR of Two Numbers in an Array — Problem & Solution
Maximum XOR of Two Numbers in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum XOR of Two Numbers in an Array is a medium coding problem on arrays, hash table and bit manipulation, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Bit Manipulation, Trie
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, return the maximum value of nums[i] XOR nums[j] over all pairs of indices 0 <= i <= j < n.
Example 1
Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: 5 XOR 25 = 28.
Example 2
Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127
Example 3
Input: nums = [0]
Output: 0
Constraints
1 <= nums.length <= 400 <= nums[i] <= 1000000000
Follow-up: The O(n²) scan is easy. Can you get O(32n) with a bit trie or a prefix hash set?
Hints for Maximum XOR of Two Numbers in an Array
Hint 1
Build the answer one bit at a time, from the most significant bit down.
Hint 2
Keep the prefixes of every number under a growing mask in a hash set.
Hint 3
If two prefixes
pandqsatisfyp ^ q == candidate, that bit is achievable — a set lookup forcandidate ^ pdecides it.
How to solve Maximum XOR of Two Numbers in an Array
Build the answer greedily bit by bit from the top: keep the prefixes under a growing mask in a set, and test whether some pair of prefixes XORs to the current candidate.
Approach
- For each bit from 31 down: extend the mask, collect
x & maskfor allx. - Set
candidate = best | (1 << bit); if any prefixphascandidate ^ pin the set, acceptbest = candidate.
Why it works
A higher bit is worth more than all lower bits combined, so committing to the best achievable prefix at each level is optimal; p ^ q == candidate is checked in O(1) via candidate ^ p ∈ set.
Complexity
- Time —
O(32 · n) - Space —
O(n)
Pitfalls
- A binary trie is the equivalent structural approach and handles streaming queries.
Reference solution
Python
def findMaximumXOR(nums) -> int:
best = 0
mask = 0
for bit in range(31, -1, -1):
mask |= 1 << bit
prefixes = {x & mask for x in nums}
candidate = best | (1 << bit)
if any((candidate ^ p) in prefixes for p in prefixes):
best = candidate
return bestJava
public static int findMaximumXOR(int[] nums) {
int best = 0, mask = 0;
for (int bit = 30; bit >= 0; bit--) {
mask |= 1 << bit;
Set<Integer> prefixes = new HashSet<>();
for (int x : nums) prefixes.add(x & mask);
int candidate = best | (1 << bit);
for (int p : prefixes) {
if (prefixes.contains(candidate ^ p)) {
best = candidate;
break;
}
}
}
return best;
}C++
int findMaximumXOR(vector<int>& nums) {
int best = 0, mask = 0;
for (int bit = 30; bit >= 0; bit--) {
mask |= 1 << bit;
unordered_set<int> prefixes;
for (int x : nums) prefixes.insert(x & mask);
int candidate = best | (1 << bit);
for (int p : prefixes) {
if (prefixes.count(candidate ^ p) > 0) {
best = candidate;
break;
}
}
}
return best;
}JavaScript
var findMaximumXOR = function(nums) {
let best = 0;
let mask = 0;
for (let bit = 31; bit >= 0; bit--) {
mask = mask | (1 << bit);
const prefixes = new Set();
for (let i = 0; i < nums.length; i++) prefixes.add((nums[i] & mask) >>> 0);
const candidate = (best | (1 << bit)) >>> 0;
let found = false;
prefixes.forEach(function(p) {
if (prefixes.has((candidate ^ p) >>> 0)) found = true;
});
if (found) best = candidate;
}
return best | 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets