Lesson 19.4 · Trie
The Binary Trie for XOR
Insert numbers bit by bit from the highest bit; to maximise XOR with x, prefer the opposite bit at every level.
10 min
Think of it like this
Picking a partner most different from you: you first look for someone who differs on the most important trait, and only then on the less important ones.
1.Greedy from the top bit
XOR gives 1 where bits differ, and a 1 in bit 30 is worth more than all lower bits together. So, for a number x, walk the trie from bit 30 down: if a child with the opposite bit exists, take it (that bit of the XOR is 1); otherwise take the same bit. Each query is 31 steps.
Example: in [3, 10, 5, 25, 2, 8], 5 = 00101 and 25 = 11001 give 11100 = 28, the maximum.
Quick check
What is 5 XOR 25 in binary?
Remember
- Each level is one bit, highest first.
- Prefer the opposite bit to make the XOR bit 1.
- O(31) per insert and query.
Common mistakes
- Walking bits from low to high (greedy then fails).