You are given an array nums
consisting of non-negative integers. You are also given a queries
array, where queries[i] = [xi, mi]
.
The answer to the ith
query is the maximum bitwise XOR
value of xi
and any element of nums
that does not exceed mi
. In other words, the answer is max(nums[j] XOR xi)
for all j
such that nums[j] <= mi
. If all elements in nums
are larger than mi
, then the answer is -1
.
Return an integer array answer
where answer.length == queries.length
and answer[i]
is the answer to the ith
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 <= 105
queries[i].length == 2
0 <= nums[j], xi, mi <= 109
Companies:
Google
Related Topics:
Array, Bit Manipulation, Trie
Similar Questions:
// OJ: https://leetcode.com/problems/maximum-xor-with-an-element-from-array/
// Author: github.com/lzl124631x
// Time: O(A + Q)
// Space: O(A)
struct TrieNode {
TrieNode *next[2] = {};
int minVal = INT_MAX;
};
class Solution {
void add(TrieNode *node, int n) {
for (int i = 31; i >= 0; --i) {
int b = n >> i & 1;
if (node->next[b] == NULL) node->next[b] = new TrieNode();
node = node->next[b];
node->minVal = min(node->minVal, n);
}
}
int maxXor(TrieNode *node, int x, int m) {
int ans = 0;
for (int i = 31; i >= 0; --i) {
int b = x >> i & 1;
if (node->next[1 - b] && node->next[1 - b]->minVal <= m) {
node = node->next[1 - b];
ans |= 1 << i;
} else if (node->next[b] && node->next[b]->minVal <= m) node = node->next[b];
else return -1;
}
return ans;
}
public:
vector<int> maximizeXor(vector<int>& A, vector<vector<int>>& Q) {
TrieNode root;
vector<int> ans;
for (int n : A) add(&root, n);
for (auto &q : Q) {
int x = q[0], m = q[1];
ans.push_back(maxXor(&root, x, m));
}
return ans;
}
};
// OJ: https://leetcode.com/problems/maximum-xor-with-an-element-from-array/
// Author: github.com/lzl124631x
// Time: O(QlogQ + AlogA + Q + A)
// Space: O(Q + A)
struct TrieNode {
TrieNode *next[2] = {};
};
class Solution {
void addNumber(TrieNode *node, int val) {
for (int i = 31; i >= 0; --i) {
int b = val >> i & 1;
if (!node->next[b]) node->next[b] = new TrieNode();
node = node->next[b];
}
}
int getMaxXor(TrieNode *node, int val) {
int ans = 0;
for (int i = 31; i >= 0; --i) {
int b = val >> i & 1;
if (node->next[1 - b]) {
node = node->next[1 - b];
ans |= 1 << i;
} else {
node = node->next[b];
}
}
return ans;
}
public:
vector<int> maximizeXor(vector<int>& A, vector<vector<int>>& Q) {
for (int i = 0; i < Q.size(); ++i) Q[i].push_back(i);
sort(begin(Q), end(Q), [](auto &a, auto &b) { return a[1] < b[1]; });
sort(begin(A), end(A));
vector<int> ans(Q.size());
TrieNode root;
int i = 0;
for (int j = 0; j < Q.size(); ++j) {
int x = Q[j][0], m = Q[j][1], index = Q[j][2];
while (i < A.size() && A[i] <= m) addNumber(&root, A[i++]);
ans[index] = i == 0 ? -1 : getMaxXor(&root, x);
}
return ans;
}
};