Best XOR Partner Under a Cap

Hard

You get an array of non-negative integers values and a list of queries queries, where queries[i] = [x, cap]. The answer to a query is the largest x XOR v over all elements v of the array that do not exceed cap. If there are none (every element is above cap), the answer is -1. Return the answers in query order.

Example 1

values=[3, 10, 6, 12], queries=[[5, 7], [9, 2], [1, 20]] → [6, -1, 13]

For [5, 7] the allowed numbers are 3 and 6: 5 XOR 3 = 6 and 5 XOR 6 = 3, so the answer is 6. For [9, 2] every number exceeds 2, so the answer is -1. For [1, 20] all numbers qualify, and the best is 1 XOR 12 = 13.

Example 2

values=[0, 0, 8], queries=[[8, 0], [7, 8]] → [8, 15]

With cap 0 only 0 is available: 8 XOR 0 = 8. With cap 8: 7 XOR 8 = 15.

Constraints

1 ≤ len(values), len(queries) ≤ 10⁵
0 ≤ values[j] ≤ 10⁹
0 ≤ x, cap ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Trie Array

Similar problems

Words That Fit Each Puzzle Hard Pairs With XOR in a Range Hard Best XOR Up the Chain of Command Hard Largest XOR of a Close Pair Hard Most Different Pair Medium

Input

values=[3, 10, 6, 12], queries=[[5, 7], [9, 2], [1, 20]]

Expected

[6, -1, 13]

Run checks the first 3 tests in your browser. Submit checks all 80 tests on the server, hidden ones included.