Maximum XOR with Limit

Problem statement

Given an array of integers nums and an array of queries in the format of (x, limit), for every query in the form of (x, limit), return the maximum value of XOR between the value x and any integer from the array such that the array element should be less than or equal to the limit. If all elements in nums are larger than the limit, return -1.

Example

Sample input

Sample output

Explanation

Query 1:
The array elements not greater than the limit 3 are [0, 1, 2, 3]
0 XOR 3 = 3
1 XOR 3 = 2
2 XOR 3 = 1
3 XOR 3 = 0
answer = max(3,2,1,0) = 3

Query 2:
The array elements not greater than the limit 1 are [0, 1]
0 XOR 4 = 4
1 XOR 4 = 5
answer = max(4,5) = 5

Query 3:
The array elements not greater than the limit 17 are [0, 1, 2, 3, 4]
0 XOR 5 = 5
1 XOR 5 = 4
2 XOR 5 = 7
3 XOR 5 = 6
4 XOR 5 = 1
answer = max(5,4,7,6,1) = 7

Try it yourself

Try to solve the problem yourself before reading the solution.

Prerequisite

The requirements of this problem are similar to the problem maximum XOR of two numbers in an array. We suggest you go through the linked problem before you move forward here.

Intuition

In this problem, we need to consider an extra requirement when calculating the XOR—which is that the array elements should not be greater than the limit value. For this, we can create a different trie for each query, choosing only the elements smaller or equal to the limit, and find the maximum XOR value with the value x. But this approach requires us to create too many tries, essentially one for each query.

One way to solve this problem is by sorting the input array nums and the query limit in ascending order. Sorting the queries based on the limit ensures that the trie only contains integers that are less than the limit at any time. Therefore, the problem boils down to only finding the maximum XOR of the currently given integer with the integers already existing in the trie. This way, we can answer all the queries by constructing a single trie. 

For example:

1. Let's say we have the inputs:
   nums: [4, 3, 2, 1, 0]
queries: [[1, 3], [4, 1], [5, 17]

2. We'll sort the nums array and queries based on the limit value, so the values become:
   queries: [[4, 1], [1, 3], [5, 17]
nums: [0, 1, 2, 3, 4]

3. For the first query [4, 1], which has limit = 1, we add the values [0, 1] from the nums array in the trie. Next we calculate the max XOR value of x = 4 with the trie containing [0, 1].

4. For the second query [1, 3], with limit = 3, we add the values [2, 3] from the nums array in the trie. Next we calculate the max XOR value of x = 1 with the trie containing [0, 1, 2, 3].

5. For the third query [5, 17], with limit = 17, we add the value [4] from the nums array in the trie. Next we calculate the max XOR value of x = 5 with the trie containing [0, 1, 2, 3, 4].

Algorithm

To prevent the creation of a separate trie for every query, we can adopt the following algorithm.

Step 1: Sorting the input and the queries

Sort the input nums array. Then, sort the queries based on the limit value so the query with the lowest limit value is at the start.

One important thing to note here is that the answers we calculate in the above algorithms would be in a different order than the queries since we sorted the queries array. To solve this, we attach an extra parameter index to the queries at the start before sorting them. Then, once we have the answers to all the queries at the end, we can sort them back to their original position using the index value.

Step 2: Processing the queries

For each query, perform two steps:

• Iterate over the input array and insert the elements into the trie that are less than or equal to the limit value of the current query. This ensures that at every point, all the elements present in the trie are less than or equal to the limit.

• Apply the same logic as in the maximum XOR problem to find the maximum XOR of the value x with the integers present in the trie.

Visualization

The picture below demonstrates the procedure for solving the queries.

Complexity analysis

Variables

• Number of integers in list =$N$ ...