897. Bounded XOR Queries
A telemetry team stores non-negative sensor codes in nums. Each query is a pair [x, limit]: among the stored codes that are at most limit, find the one whose bitwise XOR with x is largest, and report that XOR value.
Return an array with one answer per query, in the order the queries were given. If no stored code is at most limit, the answer for that query is -1. Codes may repeat. Comparing every query with every code costs O(n * q), which is too slow; aim for roughly O((n + q) * 30 + (n + q) log(n + q)) time using an offline sweep and a binary trie.
Example 1
- Input:
- nums = [6,11,19,4], queries = [[5,10],[13,3],[8,19]]
- Output:
- [3,-1,27]
- Explanation:
Query 1 may use 6 or 4 (best 5^6=3); query 2 has no code at most 3; query 3 may use any code and 19^8=27 is largest.
Example 2
- Input:
- nums = [7,7,7], queries = [[0,7],[7,7],[1,100]]
- Output:
- [7,0,6]
- Explanation:
Equal codes behave like one code: 0^7=7, 7^7=0 and 1^7=6.
Example 3
- Input:
- nums = [40,9,33,12], queries = [[2,8],[2,9],[30,40]]
- Output:
- [-1,11,63]
- Explanation:
With limit 8 nothing qualifies; with limit 9 only 9 does (2^9=11); with limit 40 the best partner of 30 is 33 (30^33=63).
Constraints
1 ≤ nums.length, queries.length ≤ 104
0 ≤ nums[i], x, limit ≤ 109
Every query has exactly two numbers: queries[i] = [x, limit].
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O((n + q) * 30 + n log n + q log q)
- Space
- O(30 * n)