Maximum XOR of Two Numbers (Trie)

hard

Use bitwise trie to maximize xor value

Maximum XOR of Two Numbers

Key Insight

At each bit level, prefer the opposite bit in trie to maximize XOR contribution.

Step 1Start with First Value
3
3
=
0
0
0
0
0
0
1
1
76543210

Build trie from 3 (00000011).

1 / 4

Learn the Pattern

Bit ManipulationUse bitwise operations to solve problems efficiently by treating integers as arrays of bits.
Practice the Code

Step-by-Step Walkthrough: Maximum XOR of Two Numbers

At each bit level, prefer the opposite bit in trie to maximize XOR contribution.

  1. Start with First Value

    Build trie from 3 (00000011).

  2. Add 10 and Query

    Insert 10 (00001010), then query it. Greedy opposite-bit traversal gives 9.

  3. Insert 5 and Improve

    Insert 5 (00000101) and query it. Best partner becomes 10 -> xor 15.

  4. Insert 25 for Global Maximum

    Insert 25 (11001). Querying it finds partner 5 with xor 28, the final maximum.