hardTriesPure DSA~40 min
Maximum XOR With a Bounded Element
For each query you are given a probe value and a ceiling. You must find the stored fingerprint not exceeding the ceiling that maximizes XOR with the probe. Answer all queries efficiently.
Problem
Given an integer array nums and a list of queries where queries[i] = [x_i, m_i], for each query return the maximum value of x_i XOR nums[j] over all nums[j] <= m_i, or -1 if no such element exists.
Input
An integer array nums and a list queries of [x, m] pairs.
Output
An integer array of the same length as queries with each answer (or -1).
Constraints
- 1 <= nums.length, queries.length <= 100000
- 0 <= nums[j], x_i, m_i <= 10^9
Examples
Example 1
Input
nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output
[3,3,7]
Query [3,1]: only 0,1 allowed, max 3^... = 3. Others similar.
Example 2
Input
nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
Output
[15,-1,5]
[8,1] has no nums <= 1, so -1.