Free Tries lessonsTries · Stage 2 · Mastery · Step 1

The largest XOR of any two numbers

Build a trie of bits, then for every number, walk toward the opposite bit at each level. About 13 minutes.

Build the bit trie once

Insert every number's 30 bits into the trie first, exactly like inserting words letter by letter, but with only two possible children at each step.

Once the trie holds all the numbers, you can ask of any number: which stored number is the most different from it?

One insert per number: same shape as inserting a 30-letter word.

A smaller example: nums = [3, 5, 6] as 3 bits (011, 101, 110)

Each number is inserted as a path of bits, highest bit first, like a word with only two letters.

Move 1 of 5

Walk each number greedily

For each number, walk the trie bit by bit. At each level, if the child for the opposite bit exists, take it, and that bit becomes a 1 in the running XOR. Otherwise take the only child that exists.

Keep the best result found over every number.

Prefer opposite: take it whenever the trie has it.

No choice: if only the matching bit exists, that position is a 0, and that's fine.

In code

for b in range(3, -1, -1):
    bit = (x >> b) & 1    # from the top

Quick check

At one bit position, a number's bit is 1, and the trie has both a 0-child and a 1-child here. Which does the greedy walk take?

AThe 0-child
BThe 1-child

Show the answer

The 0-child. 1 XOR 0 = 1: taking the opposite of the number's own bit (1) makes this position a 1 in the result.

Your problem

The largest XOR of any two numbers

Given an array nums of at least two non-negative integers, return the largest value of nums[i] XOR nums[j] over every pair of different indices i and j.

Example

nums = [3, 10, 5, 25, 2, 8] → 28

2 ≤ nums.length ≤ 100,000 · 0 ≤ nums[i] < 1,073,741,824 (2^30)

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.