Hard · Binary Trie
Understand → Visualise → Practice.
A higher differing bit is worth more than every lower bit combined. A binary trie lets each number greedily seek an opposite bit at every position.
Insert fixed-width bit paths; while querying, take 1 − bit when available and set that result bit.
Store every number as a 31-bit trie path.
Prefer the opposite branch.
The greedy path gives the best partner for that number.
O(31n) time and O(31n) space, both effectively O(n).
All numbers must use the same bit width, including leading zeroes.
Read the full guide first: Bit Manipulation and Bitmask Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.