Bit PreRequisites for TRIE Problems
EasyA binary trie over the bits of a number
Problem
Learn to store numbers bit-by-bit (most significant first) in a binary trie so you can query bit patterns like maximum XOR efficiently.
Store each number as a path of its bits, so you can greedily walk to find best XOR partners.
The idea
Store each number as a fixed-length path of bits, most significant first, so every node has at most two children. Fixing the length — usually 32 — is what lets you compare two numbers bit by bit down the tree, which is the basis of every XOR trie problem.
The trick
- Always insert the same number of bits so paths line up for comparison.
- Most significant bit first: higher bits dominate the value, so greedy decisions there are safe.
- Extract bit i with `(x >> i) & 1`.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — insert 6 (110), 5 (101) Values: 6, 110, 5, 101.
1for each number, for bit from high to low:2 go to child[bit], creating it if neededInput
- array
- [6, 110, 5, 101]
Output
- answer
- —
Check yourself
2 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- insert 6 (110), 5 (101)
- Output:
- stored along bit paths
Finished the walkthrough? Add it to your streak.