Maximum XOR of Two Numbers (Trie)

Hard
Concept
Code
Loading editor...
Tap Analyze to see visualization
Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Maximum XOR of Two Numbers (Trie)

Approach

Insert numbers into a 0/1 bit trie. For each new number, greedily choose opposite bits to maximize xor at highest positions first.

Complexity Analysis

Time
O(N * B)
Space
O(N * B)

Pattern

Bitwise Trie Greedy

Why It Works

A 1 in a higher bit contributes more than all lower bits, so greedy choice of opposite child at each level maximizes total xor.

Updated Feb 2026