Maximum Xor with an element from an array
HardSort both sides and insert as the limit rises
Problem
Given nums and queries (x, limit), for each query return the max XOR of x with any nums[i] <= limit, or -1 if none.
Sort queries by limit and insert elements into a bit-trie as they qualify, then greedily maximise XOR.
The idea
Sort the numbers and sort the queries by their limit, then sweep: insert numbers into the trie as they come under the current limit, and answer each query against whatever is in the trie. This way each number is inserted once and every query sees exactly the numbers it is allowed to use.
The trick
- Offline processing — answer queries out of order, then restore the original order.
- Answer -1 when the trie is still empty for that limit.
- Sorting both sides turns a per-query filter into a single sweep.
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 — nums=[0,1,2,3,4], queries=[[3,1],[1,3],[5,6]] Values: 0, 1, 2, 3, 4.
1sort nums; sort queries by limit2insert nums <= limit into trie as you go3for each query: query max XOR of x in trieInput
- array
- [0, 1, 2, 3, 4]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
- Output:
- [3, 3, 7]
- Explanation:
- Best XOR using only elements <= the limit.
Example 2
- Input:
- nums = [5,2,4,6,6,3], queries = [[12,4],[8,1]]
- Output:
- [15, -1]
- Explanation:
- Filtered max XOR per query.
Example 3
- Input:
- nums = [1], queries = [[2,0]]
- Output:
- [-1]
- Explanation:
- No element <= 0 → -1.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.