Maximum XOR of Two Numbers in an Array
Problem
Given an integer array nums, return the maximum result of nums[i] XOR nums[j] over all pairs. Aim for O(n log V) time.
nums = [3, 10, 5, 25, 2, 8]28def find_maximum_xor(nums):
ans = mask = 0
for bit in range(31, -1, -1):
mask |= (1 << bit)
prefixes = {x & mask for x in nums}
cand = ans | (1 << bit)
for p in prefixes:
if (cand ^ p) in prefixes:
ans = cand
break
return ansfunction findMaximumXOR(nums) {
let ans = 0, mask = 0;
for (let bit = 31; bit >= 0; bit--) {
mask |= (1 << bit);
const prefixes = new Set(nums.map(x => x & mask));
const cand = ans | (1 << bit);
for (const p of prefixes) {
if (prefixes.has(cand ^ p)) { ans = cand; break; }
}
}
return ans;
}class Solution {
public int findMaximumXOR(int[] nums) {
int ans = 0, mask = 0;
for (int bit = 31; bit >= 0; bit--) {
mask |= (1 << bit);
Set<Integer> prefixes = new HashSet<>();
for (int x : nums) prefixes.add(x & mask);
int cand = ans | (1 << bit);
for (int p : prefixes) if (prefixes.contains(cand ^ p)) { ans = cand; break; }
}
return ans;
}
}int findMaximumXOR(vector<int>& nums) {
int ans = 0, mask = 0;
for (int bit = 31; bit >= 0; bit--) {
mask |= (1 << bit);
unordered_set<int> prefixes;
for (int x : nums) prefixes.insert(x & mask);
int cand = ans | (1 << bit);
for (int p : prefixes) if (prefixes.count(cand ^ p)) { ans = cand; break; }
}
return ans;
}Explanation
We want the largest XOR of any two numbers in the array. Trying all pairs is slow, so we build the answer one bit at a time, from the highest bit down, always being greedy: can we make this bit a 1 in the result?
The mask keeps only the bits we have decided on so far. For each bit we form prefixes, the set of all numbers chopped down to those top bits (x & mask). We then propose cand = ans | (1 << bit), an answer with this new bit turned on, and ask whether two prefixes can actually produce it.
The check uses a XOR fact: if a ^ b = cand then cand ^ a = b. So for each prefix p we test whether cand ^ p also exists in the set. If some pair matches, this bit is achievable, so we keep cand; otherwise we leave the bit off and move on.
Example: nums = [3, 10, 5, 25, 2, 8]. Working down the bits, the greedy search confirms each high bit of 28 is reachable, and indeed 5 ^ 25 = 28, the maximum.
Because each bit is decided with one pass over a hash set, the whole thing runs in about n times the number of bits, far faster than checking every pair.