Maximum XOR With an Element From Array
Problem
You are given an array nums of non-negative integers and a list of queries, each a pair (x, m). For every query, choose the element v of nums with v ≤ m that maximizes x XOR v and report that XOR value; if every element exceeds m, the answer is -1. Answers must be returned in the original query order. Both arrays can hold up to 10⁵ entries with values up to 10⁹, so scanning all of nums for each query is too slow.
nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]][3,3,7]def maximize_xor(nums, queries):
nums.sort()
order = sorted(range(len(queries)), key=lambda i: queries[i][1])
ans = [-1] * len(queries)
trie = {}
j = 0
for i in order:
x, limit = queries[i]
while j < len(nums) and nums[j] <= limit:
node = trie
for b in range(29, -1, -1):
bit = (nums[j] >> b) & 1
node = node.setdefault(bit, {})
j += 1
if not trie:
continue
best, node = 0, trie
for b in range(29, -1, -1):
want = 1 - ((x >> b) & 1)
if want in node:
best |= 1 << b
node = node[want]
else:
node = node[1 - want]
ans[i] = best
return ansfunction maximizeXor(nums, queries) {
nums.sort((a, b) => a - b);
const order = queries.map((q, i) => i).sort((a, b) => queries[a][1] - queries[b][1]);
const ans = new Array(queries.length).fill(-1);
const trie = {};
let j = 0;
for (const i of order) {
const [x, limit] = queries[i];
while (j < nums.length && nums[j] <= limit) {
let node = trie;
for (let b = 29; b >= 0; b--) {
const bit = (nums[j] >> b) & 1;
node = node[bit] || (node[bit] = {});
}
j++;
}
if (j === 0) continue;
let best = 0, node = trie;
for (let b = 29; b >= 0; b--) {
const want = 1 - ((x >> b) & 1);
if (node[want]) { best |= 1 << b; node = node[want]; }
else node = node[1 - want];
}
ans[i] = best;
}
return ans;
}int[] maximizeXor(int[] nums, int[][] queries) {
Arrays.sort(nums);
Integer[] order = new Integer[queries.length];
for (int i = 0; i < order.length; i++) order[i] = i;
Arrays.sort(order, (a, b) -> queries[a][1] - queries[b][1]);
int[] ans = new int[queries.length];
int[][] ch = new int[nums.length * 30 + 1][2];
int size = 1, j = 0;
for (int i : order) {
int x = queries[i][0], limit = queries[i][1];
while (j < nums.length && nums[j] <= limit) {
int node = 0;
for (int b = 29; b >= 0; b--) {
int bit = (nums[j] >> b) & 1;
if (ch[node][bit] == 0) ch[node][bit] = size++;
node = ch[node][bit];
}
j++;
}
if (j == 0) { ans[i] = -1; continue; }
int best = 0, node = 0;
for (int b = 29; b >= 0; b--) {
int want = 1 - ((x >> b) & 1);
if (ch[node][want] != 0) { best |= 1 << b; node = ch[node][want]; }
else node = ch[node][1 - want];
}
ans[i] = best;
}
return ans;
}vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
sort(nums.begin(), nums.end());
vector<int> order(queries.size()), ans(queries.size(), -1);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(),
[&](int a, int b) { return queries[a][1] < queries[b][1]; });
vector<array<int, 2>> ch(1, {0, 0});
int j = 0;
for (int i : order) {
int x = queries[i][0], limit = queries[i][1];
while (j < (int)nums.size() && nums[j] <= limit) {
int node = 0;
for (int b = 29; b >= 0; b--) {
int bit = (nums[j] >> b) & 1;
if (!ch[node][bit]) { ch[node][bit] = ch.size(); ch.push_back({0, 0}); }
node = ch[node][bit];
}
j++;
}
if (j == 0) continue;
int best = 0, node = 0;
for (int b = 29; b >= 0; b--) {
int want = 1 - ((x >> b) & 1);
if (ch[node][want]) { best |= 1 << b; node = ch[node][want]; }
else node = ch[node][1 - want];
}
ans[i] = best;
}
return ans;
}Explanation
Answering "which element of a set maximizes XOR with x?" is the classic job of a binary trie: store each number as its bits from most significant to least, then walk down for a query, taking the opposite of each of x's bits whenever that child exists. Every opposite branch we manage to take sets a 1 in the XOR at that bit position.
The greedy is safe because bit weights are powers of two: winning bit b contributes 2^b, which outweighs every lower bit combined, so a 1 secured high up can never be beaten by different choices further down.
The twist here is the per-query cap m: only elements ≤ m may be used. Rebuilding a trie for each query would be far too slow, so we go offline: sort nums, sort the queries by m, and sweep a pointer j that inserts numbers into the trie the moment a query's limit admits them. Because limits only grow, every number is inserted exactly once, and each query walks a trie containing exactly its eligible elements. If the trie is still empty, the answer is -1.
Default example: nums = [0,1,2,3,4], queries (3,1), (1,3), (5,6) are already in limit order. For (3,1) we insert 0 and 1; x=3 (011) is forced down 0 at the top bit, then grabs opposite bits to reach element 0: 3⊕0=3. For (1,3) we add 2 and 3, and the walk reaches element 2: 1⊕2=3. For (5,6) we add 4 and the walk again reaches 2: 5⊕2=7, giving [3,3,7].
Each insertion and each query walk touches one trie node per bit — 30 levels suffice for values up to 10⁹ — so after the two sorts the total work is linear in n + q with a factor of 30: O(n log n + q log q + 30(n + q)) time and O(30n) space for the trie.
The visualization pads numbers to the fewest bits the current inputs need (3 bits for the default example) so the trie stays readable; the real code simply uses a fixed 30 levels.