Maximum XOR With an Element From Array
Hard · Tries · Array · Bit Manipulation · Trie · Sorting
Problem
You are given an array nums of non-negative integers and an array queries where queries[i] = [x_i, m_i].
The answer to query i is the maximum of x_i XOR nums[j] over all j with nums[j] <= m_i. If every element of nums is greater than m_i, the answer is -1.
Return an array answer where answer[i] is the answer to the i-th query.
Examples
Input: nums = [5,2,8,1], queries = [[3,1],[6,5],[0,0]] Output: [2,7,-1]
Query [3,1] may only use 1: 3 XOR 1 = 2. Query [6,5] may use 5, 2 or 1, and 6 XOR 1 = 7 is best. No element is at most 0.
Input: nums = [10], queries = [[4,10],[7,9]] Output: [14,-1]
4 XOR 10 = 14; the limit 9 excludes the only element.
Input: nums = [0,1,2,3,4], queries = [[1,3],[5,6],[3,4]] Output: [3,7,7]
1 XOR 2 = 3 with the numbers up to 3; 5 XOR 2 = 7; 3 XOR 4 = 7.
Constraints
- 1 <= len(nums), len(queries) <= 10^5
- queries[i].length == 2
- 0 <= nums[j], x_i, m_i <= 10^9
Approaches
- Baseline: check every number for every query — time O(n · q), space O(1)
Follow-up
What if the queries arrive one at a time and must be answered immediately (online)? Store in every trie node the smallest number below it. During the walk, only step into a child whose smallest number is at most m; if neither child qualifies at the root, the answer is -1.
Related problems
Start free on Cariara · Coding problems · System design studio
