Medium

Maximum XOR of Two Numbers in an Array

LAB

Return the maximum xor obtainable from any pair of numbers.

EXAMPLES

Example 1

Input
{
  "nums": [
    3,
    10,
    5,
    25,
    2,
    8
  ]
}

Output
28

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

For each number, we want to find another number that differs in as many significant bit positions as possible, maximizing XOR.

Reveal reference solution +

pythonREFERENCE

def findMaximumXOR(self, nums: List[int]) -> int:
    trie = XORTrie()
    for num in nums:
        trie.insert(num)

    max_xor = 0
    for num in nums:
        max_xor = max(max_xor, trie.findMaxXOR(num))
    return max_xor

TimeO(n)

SpaceO(n)

Open on LeetCode ↗