Maximum XOR Pair
Problem
Given a list of non-negative integers, return the largest value obtainable by taking the bitwise XOR of two of them. The two may be the same element only if that element appears twice.
Examples
Input: nums = [3, 10, 5, 25, 2, 8]
Output: 28
Why: 5 XOR 25 is 28, and no other pair beats itInput: nums = [8, 10, 2]
Output: 10
Why: 8 XOR 2 is 10, which beats 8 XOR 10 and 10 XOR 2Input: nums = [1, 1]
Output: 0
Why: edge case, identical values cancel to zeroHints
0 / 3
Comparing every pair is O(n squared). Notice that XOR decides each bit independently, and the highest bit is worth more than all the lower ones combined.
Store the numbers as bit strings, most significant bit first, so that numbers agreeing on their top bits share a path.
Build a binary trie over the bits. For each number, walk down it choosing the opposite bit at every level when that branch exists, because a differing bit is exactly what sets a 1 in the XOR. The greedy walk gives that number's best partner in one pass.
Solution
A binary trie stores each number as a path of bits from the top down. Because the highest differing bit dominates the result, the best partner for a number is found by always steering toward the opposite bit and only falling back when that branch is empty — a greedy choice that is safe precisely because one high bit outweighs every lower bit together. Each of the n numbers is inserted once and queried once over b bits, giving O(n·b) time and O(n·b) space instead of O(n²).
def max_xor(nums):
bits = max(max(nums).bit_length(), 1)
root = {}
for n in nums: # insert, most significant first
node = root
for b in range(bits - 1, -1, -1):
node = node.setdefault((n >> b) & 1, {})
best = 0
for n in nums:
node, value = root, 0
for b in range(bits - 1, -1, -1):
want = 1 - ((n >> b) & 1) # a differing bit sets a 1
if want in node:
value |= 1 << b
node = node[want]
else:
node = node[1 - want]
best = max(best, value)
return best
print(max_xor([3, 10, 5, 25, 2, 8]), max_xor([8, 10, 2]), max_xor([1, 1])) # -> 28 10 0Stuck on the idea rather than the code? Trie vs Hash Set covers it.