Formatted question description: https://leetcode.ca/all/1707.html
1707. Maximum XOR With an Element From Array
Level
Hard
Description
You are given an array nums
consisting of non-negative integers. You are also given a queries
array, where queries[i] = [x_i, m_i]
.
The answer to the i-th
query is the maximum bitwise XOR
value of x_i
and any element of nums
that does not exceed m_i
. In other words, the answer is max(nums[j] XOR x_i)
for all j
such that nums[j] <= m_i
. If all elements in nums
are larger than m_i
, then the answer is -1
.
Return an integer array answer
where answer.length == queries.length
and answer[i]
is the answer to the i-th
query.
Example 1:
Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
Output: [3,3,7]
Explanation:**
1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.
Example 2:
Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
Output: [15,-1,5]
Constraints:
1 <= nums.length, queries.length <= 10^5
queries[i].length == 2
0 <= nums[j], x_i, m_i <= 10^9
Solution
Create a trie from the numbers in nums
. Each node in the trie has two children that represent bits 0 and 1, respectively. For each number, create the trie from the highest bit to the lowest bit, where all the numbers have 32 bits. For each node in the trie, maintain the minimum number in nums
that can reach the node.
Then for each query, obtain the values x
and m
, and use x
to find the maximum possible xor result. If the last bit is met and the minimum value of the last bit is less than or equal to m
, then calculate the xor value accordingly. Otherwise, the query result is -1.
Finally, return the query results.
Java
class Solution {
public int[] maximizeXor(int[] nums, int[][] queries) {
TrieNode root = new TrieNode();
for (int num : nums) {
TrieNode node = root;
for (int i = 31; i >= 0; i--) {
int bit = (num & (1 << i)) == 0 ? 0 : 1;
if (node.children[bit] == null)
node.children[bit] = new TrieNode();
node = node.children[bit];
node.min = Math.min(node.min, num);
}
node.isEnd = true;
}
int queriesCount = queries.length;
int[] maxXors = new int[queriesCount];
for (int i = 0; i < queriesCount; i++) {
int xor = 0;
int[] query = queries[i];
int x = query[0], m = query[1];
TrieNode node = root;
boolean flag = true;
for (int j = 31; j >= 0; j--) {
int bit = (x & (1 << j)) == 0 ? 1 : 0;
if (node.children[bit] != null && node.children[bit].min <= m) {
if (bit == 1)
xor ^= 1 << j;
node = node.children[bit];
} else if (node.children[1 - bit] != null && node.children[1 - bit].min <= m) {
if (bit == 0)
xor ^= 1 << j;
node = node.children[1 - bit];
} else {
flag = false;
break;
}
}
if (node.isEnd && flag)
maxXors[i] = xor ^ x;
else
maxXors[i] = -1;
}
return maxXors;
}
}
class TrieNode {
int min = Integer.MAX_VALUE;
boolean isEnd;
TrieNode[] children;
public TrieNode() {
children = new TrieNode[2];
isEnd = false;
}
}