Trie (Prefix Tree)
Store strings or binary numbers on the edges of a tree so prefix questions and maximum-XOR questions take time proportional to the length, not the count.
The problem
Two questions that look unrelated share one answer.
- You store words. How many of them start with a given prefix such as
app? - You store numbers. Which one gives the largest XOR (bitwise exclusive or: each bit is 1 when the two input bits differ) with a number ?
Both ask about the leading part of an item: leading letters, or leading bits.
1 of 9