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 <= 105queries[i].length == 20 <= nums[j], xi, mi <= 109
class Trie:
def __init__(self):
self.children = [None] * 2
def insert(self, x):
node = self
for i in range(30, -1, -1):
v = (x >> i) & 1
if node.children[v] is None:
node.children[v] = Trie()
node = node.children[v]
def search(self, x):
node = self
ans = 0
for i in range(30, -1, -1):
v = (x >> i) & 1
if node.children[v ^ 1]:
ans |= 1 << i
node = node.children[v ^ 1]
elif node.children[v]:
node = node.children[v]
else:
return -1
return ans
class Solution:
def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
trie = Trie()
nums.sort()
j, n = 0, len(queries)
ans = [-1] * n
for i, (x, m) in sorted(zip(range(n), queries), key=lambda x: x[1][1]):
while j < len(nums) and nums[j] <= m:
trie.insert(nums[j])
j += 1
ans[i] = trie.search(x)
return ansclass Solution {
public int[] maximizeXor(int[] nums, int[][] queries) {
Trie trie = new Trie();
Arrays.sort(nums);
int n = queries.length;
int[] ans = new int[n];
int[][] qs = new int[n][3];
for (int i = 0; i < n; ++i) {
qs[i] = new int[] {i, queries[i][0], queries[i][1]};
}
Arrays.sort(qs, (a, b) -> a[2] - b[2]);
int j = 0;
for (var q : qs) {
int i = q[0], x = q[1], m = q[2];
while (j < nums.length && nums[j] <= m) {
trie.insert(nums[j++]);
}
ans[i] = trie.search(x);
}
return ans;
}
}
class Trie {
Trie[] children = new Trie[2];
public void insert(int x) {
Trie node = this;
for (int i = 30; i >= 0; --i) {
int v = (x >> i) & 1;
if (node.children[v] == null) {
node.children[v] = new Trie();
}
node = node.children[v];
}
}
public int search(int x) {
Trie node = this;
int ans = 0;
for (int i = 30; i >= 0; --i) {
int v = (x >> i) & 1;
if (node.children[v ^ 1] != null) {
ans |= 1 << i;
node = node.children[v ^ 1];
} else if (node.children[v] != null) {
node = node.children[v];
} else {
return -1;
}
}
return ans;
}
}class Trie {
public:
Trie()
: children(2) {}
void insert(int x) {
Trie* node = this;
for (int i = 30; ~i; --i) {
int v = (x >> i) & 1;
if (!node->children[v]) {
node->children[v] = new Trie();
}
node = node->children[v];
}
}
int search(int x) {
int ans = 0;
Trie* node = this;
for (int i = 30; ~i; --i) {
int v = (x >> i) & 1;
if (node->children[v ^ 1]) {
node = node->children[v ^ 1];
ans |= 1 << i;
} else if (node->children[v]) {
node = node->children[v];
} else {
return -1;
}
}
return ans;
}
private:
vector<Trie*> children;
};
class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
sort(nums.begin(), nums.end());
int n = queries.size();
vector<tuple<int, int, int>> qs;
for (int i = 0; i < n; ++i) {
qs.push_back({queries[i][1], queries[i][0], i});
}
sort(qs.begin(), qs.end());
Trie* trie = new Trie();
int j = 0;
vector<int> ans(n);
for (auto& [m, x, i] : qs) {
while (j < nums.size() && nums[j] <= m) {
trie->insert(nums[j++]);
}
ans[i] = trie->search(x);
}
return ans;
}
};type Trie struct {
children [2]*Trie
}
func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(x int) {
node := this
for i := 30; i >= 0; i-- {
v := (x >> i) & 1
if node.children[v] == nil {
node.children[v] = newTrie()
}
node = node.children[v]
}
}
func (this *Trie) search(x int) int {
node := this
ans := 0
for i := 30; i >= 0; i-- {
v := (x >> i) & 1
if node.children[v^1] != nil {
node = node.children[v^1]
ans |= 1 << i
} else if node.children[v] != nil {
node = node.children[v]
} else {
return -1
}
}
return ans
}
func maximizeXor(nums []int, queries [][]int) []int {
sort.Ints(nums)
type tuple struct{ i, x, m int }
n := len(queries)
qs := make([]tuple, n)
for i, q := range queries {
qs[i] = tuple{i, q[0], q[1]}
}
sort.Slice(qs, func(i, j int) bool { return qs[i].m < qs[j].m })
j := 0
ans := make([]int, n)
trie := newTrie()
for _, q := range qs {
i, x, m := q.i, q.x, q.m
for j < len(nums) && nums[j] <= m {
trie.insert(nums[j])
j++
}
ans[i] = trie.search(x)
}
return ans
}