Maximum XOR With an Element From Array
Description
Given an array of non-negative integers nums and a list of queries where each query is a pair [xi, mi], determine the maximum bitwise XOR between xi and any element from nums that is at most mi.
Formally, for the i-th query, compute max(nums[j] XOR xi) across all indices j satisfying nums[j] <= mi. If every element in nums exceeds mi, the answer for that query is -1.
Return an array of integers where each entry holds the result for the corresponding query.
Examples
Example 1
Input: nums = [0, 1, 2, 3, 4], queries = [[3, 1], [1, 3], [5, 6]]
Output: [3, 3, 7]
Explanation:
- Query [3, 1]: Elements not exceeding 1 are {0, 1}. XOR values: 3 XOR 0 = 3, 3 XOR 1 = 2. Maximum is 3.
- Query [1, 3]: Elements not exceeding 3 are {0, 1, 2, 3}. XOR values: 1 XOR 0 = 1, 1 XOR 1 = 0, 1 XOR 2 = 3, 1 XOR 3 = 2. Maximum is 3.
- Query [5, 6]: All elements qualify (all ≤ 6). XOR values: 5 XOR 0 = 5, 5 XOR 1 = 4, 5 XOR 2 = 7, 5 XOR 3 = 6, 5 XOR 4 = 1. Maximum is 7.
Example 2
Input: nums = [5, 2, 4, 6, 6, 3], queries = [[12, 4], [8, 1], [6, 3]]
Output: [15, -1, 5]
Explanation:
- Query [12, 4]: Elements not exceeding 4 are {2, 4, 3}. XOR values: 12 XOR 2 = 14, 12 XOR 4 = 8, 12 XOR 3 = 15. Maximum is 15.
- Query [8, 1]: No elements are ≤ 1 (the smallest is 2). Answer is -1.
- Query [6, 3]: Elements not exceeding 3 are {2, 3}. XOR values: 6 XOR 2 = 4, 6 XOR 3 = 5. Maximum is 5.
Constraints
- 1 ≤ nums.length, queries.length ≤ 10^5
- queries[i].length == 2
- 0 ≤ nums[j], xi, mi ≤ 10^9
Editorial
Brute Force
Intuition
The most direct approach is to answer each query independently. For a query [xi, mi], scan through every element in nums, check whether the element satisfies the constraint (element ≤ mi), and if it does, compute the bitwise XOR with xi. Keep track of the largest XOR encountered.
Imagine you have a basket of numbered balls and someone asks: "Pick any ball whose number is at most 3, then combine its number with 5 using the XOR operation. Which ball gives the largest result?" You would simply try every qualifying ball one by one and compare results. That is exactly the brute force strategy: exhaustive enumeration.
Step-by-Step Explanation
Let's trace through query [3, 1] with nums = [0, 1, 2, 3, 4]:
Step 1: Initialize max_xor = -1. We have xi = 3 and mi = 1. We need the maximum XOR of 3 with any element that does not exceed 1.
Step 2: Check nums[0] = 0. Is 0 ≤ 1? Yes. Compute XOR: 3 XOR 0 = 3. Since 3 > -1, update max_xor = 3.
Step 3: Check nums[1] = 1. Is 1 ≤ 1? Yes. Compute XOR: 3 XOR 1 = 2. Since 2 < 3, max_xor stays 3.
Step 4: Check nums[2] = 2. Is 2 ≤ 1? No. Skip this element entirely.
Step 5: Check nums[3] = 3. Is 3 ≤ 1? No. Skip.
Step 6: Check nums[4] = 4. Is 4 ≤ 1? No. Skip.
Step 7: All elements checked. The answer for query [3, 1] is max_xor = 3.
Brute Force — Scanning All Elements for Query [3, 1] — For each element, check if it is within the limit mi, compute XOR with xi if valid, and track the maximum XOR value.
Algorithm
- For each query (xi, mi):
- Initialize max_xor = -1
- For each element num in nums:
- If num ≤ mi, compute xor_val = xi XOR num
- If xor_val > max_xor, update max_xor
- Store max_xor as this query's answer
- Return the array of answers
Code
class Solution {
public:
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
int q = queries.size();
vector<int> result(q);
for (int i = 0; i < q; i++) {
int xi = queries[i][0], mi = queries[i][1];
int maxXor = -1;
for (int num : nums) {
if (num <= mi) {
maxXor = max(maxXor, xi ^ num);
}
}
result[i] = maxXor;
}
return result;
}
};class Solution:
def maximizeXor(self, nums: list[int], queries: list[list[int]]) -> list[int]:
result = []
for xi, mi in queries:
max_xor = -1
for num in nums:
if num <= mi:
max_xor = max(max_xor, xi ^ num)
result.append(max_xor)
return resultclass Solution {
public int[] maximizeXor(int[] nums, int[][] queries) {
int q = queries.length;
int[] result = new int[q];
for (int i = 0; i < q; i++) {
int xi = queries[i][0], mi = queries[i][1];
int maxXor = -1;
for (int num : nums) {
if (num <= mi) {
maxXor = Math.max(maxXor, xi ^ num);
}
}
result[i] = maxXor;
}
return result;
}
}Complexity Analysis
Time Complexity: O(q × n)
For each of the q queries, we scan every one of the n elements in nums. Each iteration does a constant-time comparison and XOR operation. With q and n both up to 10^5, the worst case is 10^10 operations.
Space Complexity: O(1) (excluding the output array)
We use only a handful of integer variables (max_xor, xor_val, etc.) per query. No auxiliary data structures are allocated.
Why This Approach Is Not Efficient
The brute force performs up to q × n operations. With both q and n reaching 10^5, that is up to 10^10 operations — far beyond what any judge can execute within a few seconds.
The root cause is twofold:
- Redundant scanning: For every query we re-examine the entire array, including elements that exceed mi and contribute nothing.
- Linear XOR search: Even among valid elements, we compute XOR with every single one, when in principle we only need the element whose bits differ the most from xi.
Key insight: XOR is maximized when the two numbers differ at the most significant bit first. If we could organize numbers by their bit patterns — specifically in a binary trie — we could greedily pick the opposite bit at each level and find the best XOR partner in O(30) time (one step per bit) instead of O(n).
Better Approach - Binary Trie
Intuition
To maximize XOR, we want the result to have as many 1-bits as possible, starting from the most significant bit (MSB). A bit in the XOR result is 1 only when the corresponding bits of the two operands differ.
A binary trie stores each number as a path of 31 bits (sufficient for values up to 10^9). From the root, each level represents one bit position (MSB first). At every node there are at most two children: one for bit 0 and one for bit 1.
To find the maximum XOR with a query value xi, we traverse the trie from the root. At each level, we look at the current bit of xi and try to follow the opposite child — because opposite bits produce a 1 in the XOR result. If the opposite child does not exist, we settle for the same-bit child. After 31 levels, we reach a leaf and the accumulated result is the maximum possible XOR.
For this approach, we sort nums so we can quickly identify elements ≤ mi, build a fresh trie from those valid elements for each query, and search it. This introduces the critical data structure but is still wasteful because we rebuild the trie from scratch for every query.
Step-by-Step Explanation
Let's trace query [3, 1] from Example 1 using a 3-bit trie (sufficient for values 0–4).
nums (sorted) = [0, 1, 2, 3, 4]. For this query xi = 3, mi = 1.
Step 1: Identify valid elements. Scan sorted nums: 0 ≤ 1 ✓, 1 ≤ 1 ✓, 2 > 1 ✗ — stop. Valid set: {0, 1}.
Step 2: Build trie — insert 0 (binary 000). Create path root → 0 → 0 → 0 (leaf).
Step 3: Insert 1 (binary 001). Path diverges at bit 0: root → 0 → 0 → 1 (new leaf). Trie now stores both 0 and 1.
Step 4: Begin search for max XOR with xi = 3 (binary 011). Start at root.
Step 5: Bit 2 (MSB): xi's bit is 0. We want the opposite bit 1 to maximize XOR. Root has no child 1 — only child 0. Forced to follow 0. XOR bit = 0.
Step 6: Bit 1: xi's bit is 1. We want 0. Child 0 exists. Follow it. XOR bit = 1. Running result = 10₂ = 2.
Step 7: Bit 0 (LSB): xi's bit is 1. We want 0. Child 0 exists (this is element 0). Follow it. XOR bit = 1. Final result = 11₂ = 3.
Step 8: Reached leaf for element 0 (000₂). max XOR = 3 XOR 0 = 3. Answer for this query is 3.
Binary Trie — Build and Search for Query [3, 1] — Watch how we build a binary trie from valid elements, then greedily traverse it seeking opposite bits to maximize XOR.
Algorithm
- Sort nums in ascending order
- For each query (xi, mi):
a. Build a fresh binary trie from all elements in nums that are ≤ mi (stop early since nums is sorted)
b. If no elements qualified, answer is -1
c. Otherwise, search the trie greedily:- For each bit from bit 30 down to bit 0:
- Compute the current bit of xi
- Try to follow the child with the opposite bit
- If the opposite child exists, set that bit in the result and follow it
- Otherwise, follow the same-bit child
d. The accumulated result is the maximum XOR for this query
- For each bit from bit 30 down to bit 0:
- Return all answers
Code
class Solution {
public:
struct TrieNode {
TrieNode* children[2] = {nullptr, nullptr};
};
void insert(TrieNode* root, int num) {
TrieNode* node = root;
for (int bit = 30; bit >= 0; bit--) {
int b = (num >> bit) & 1;
if (!node->children[b])
node->children[b] = new TrieNode();
node = node->children[b];
}
}
int search(TrieNode* root, int xi) {
TrieNode* node = root;
int maxXor = 0;
for (int bit = 30; bit >= 0; bit--) {
int b = (xi >> bit) & 1;
int want = b ^ 1;
if (node->children[want]) {
maxXor |= (1 << bit);
node = node->children[want];
} else if (node->children[b]) {
node = node->children[b];
} else {
return -1;
}
}
return maxXor;
}
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
sort(nums.begin(), nums.end());
int q = queries.size();
vector<int> result(q);
for (int i = 0; i < q; i++) {
int xi = queries[i][0], mi = queries[i][1];
TrieNode* root = new TrieNode();
bool inserted = false;
for (int num : nums) {
if (num > mi) break;
insert(root, num);
inserted = true;
}
result[i] = inserted ? search(root, xi) : -1;
}
return result;
}
};class TrieNode:
def __init__(self):
self.children = [None, None]
class Solution:
def maximizeXor(self, nums: list[int], queries: list[list[int]]) -> list[int]:
nums.sort()
result = []
for xi, mi in queries:
root = TrieNode()
inserted = False
for num in nums:
if num > mi:
break
inserted = True
node = root
for bit in range(30, -1, -1):
b = (num >> bit) & 1
if node.children[b] is None:
node.children[b] = TrieNode()
node = node.children[b]
if not inserted:
result.append(-1)
continue
node = root
max_xor = 0
for bit in range(30, -1, -1):
b = (xi >> bit) & 1
want = b ^ 1
if node.children[want]:
max_xor |= (1 << bit)
node = node.children[want]
elif node.children[b]:
node = node.children[b]
else:
max_xor = -1
break
result.append(max_xor)
return resultclass Solution {
static class TrieNode {
TrieNode[] children = new TrieNode[2];
}
private void insert(TrieNode root, int num) {
TrieNode node = root;
for (int bit = 30; bit >= 0; bit--) {
int b = (num >> bit) & 1;
if (node.children[b] == null)
node.children[b] = new TrieNode();
node = node.children[b];
}
}
private int search(TrieNode root, int xi) {
TrieNode node = root;
int maxXor = 0;
for (int bit = 30; bit >= 0; bit--) {
int b = (xi >> bit) & 1;
int want = b ^ 1;
if (node.children[want] != null) {
maxXor |= (1 << bit);
node = node.children[want];
} else if (node.children[b] != null) {
node = node.children[b];
} else {
return -1;
}
}
return maxXor;
}
public int[] maximizeXor(int[] nums, int[][] queries) {
Arrays.sort(nums);
int q = queries.length;
int[] result = new int[q];
for (int i = 0; i < q; i++) {
int xi = queries[i][0], mi = queries[i][1];
TrieNode root = new TrieNode();
boolean inserted = false;
for (int num : nums) {
if (num > mi) break;
insert(root, num);
inserted = true;
}
result[i] = inserted ? search(root, xi) : -1;
}
return result;
}
}Complexity Analysis
Time Complexity: O(n log n + q × k × 31)
Sorting nums takes O(n log n). For each of the q queries, we insert up to k valid elements into a fresh trie (k × 31 operations for 31-bit paths) and perform one search (31 operations). In the worst case k = n, giving O(n log n + q × n × 31). While the per-search cost is now O(31) instead of O(n), the trie rebuild cost dominates.
Space Complexity: O(k × 31) per query
Each inserted number creates at most 31 new trie nodes. In the worst case, all n numbers are inserted, using O(31n) nodes. The trie is rebuilt and discarded for every query.
Why This Approach Is Not Efficient
Although the binary trie reduces each individual XOR search to O(31), the overall approach is not faster than brute force in the worst case because we rebuild the entire trie from scratch for every query.
Consider two consecutive queries with mi = 1000 and mi = 1001. The second query's valid set contains almost the same elements as the first, yet we discard the first trie and build a new one from scratch. This is massively redundant.
The key observation is: if we sort queries by mi in ascending order, each query's valid set is a superset of the previous query's valid set. Elements that qualified for query k also qualify for query k+1 (because mi only increases). So instead of rebuilding, we can incrementally add new elements to a single trie that persists across queries.
This offline sorting insight transforms the total insertion work from O(q × n × 31) to O(n × 31) — each element is inserted exactly once across all queries.
Optimal Approach - Offline Queries with Binary Trie
Intuition
The optimal approach combines two ideas:
- Binary trie for greedy XOR maximization — same trie structure as before, giving O(31) per search.
- Offline query processing — sort queries by mi in ascending order so we can build the trie incrementally.
Here is the strategy:
- Sort nums in ascending order.
- Attach each query's original index (so we can place answers back in the right position), then sort queries by their mi values.
- Maintain a single trie and a pointer j into the sorted nums array.
- Process queries in ascending mi order. For each query, advance j to insert all new elements that became valid (nums[j] ≤ mi). These elements stay in the trie permanently — they will be valid for all subsequent queries too.
- Search the trie for max XOR with xi.
This way, every element is inserted into the trie exactly once across all queries. The total work is O(n × 31) for insertions and O(q × 31) for searches, plus O(n log n + q log q) for sorting.
Step-by-Step Explanation
Let's trace Example 1: nums = [0, 1, 2, 3, 4], queries = [[3, 1], [1, 3], [5, 6]].
Using 3-bit representations for clarity (real implementation uses 31 bits).
Preparation:
- Sorted nums: [0, 1, 2, 3, 4]
- Queries with original indices, sorted by mi: (idx=0, [3,1]), (idx=1, [1,3]), (idx=2, [5,6])
- Pointer j = 0 into sorted nums. Empty trie.
Step 1: Process Query 0: xi = 3, mi = 1. Insert elements ≤ 1.
Step 2: Insert nums[0] = 0 (binary 000). Trie gets path root → 0 → 0 → 0. Advance j to 1.
Step 3: Insert nums[1] = 1 (binary 001). Trie branches at bit 0. Advance j to 2. Next element nums[2] = 2 > 1, stop inserting.
Step 4: Search trie for max XOR with xi = 3 (011). Bit 2: xi bit = 0, want 1, no child 1, go 0.
Step 5: Bit 1: xi bit = 1, want 0, child 0 exists, go 0. XOR += 2.
Step 6: Bit 0: xi bit = 1, want 0, child 0 exists, go 0. XOR += 1. Total = 3. Reached element 0.
Step 7: ans[0] = 3. The trie persists — we do NOT rebuild it.
Step 8: Process Query 1: xi = 1, mi = 3. Insert new elements ≤ 3 starting from j = 2.
Step 9: Insert nums[2] = 2 (010) and nums[3] = 3 (011). j advances to 4. nums[4] = 4 > 3, stop. Trie now contains {0, 1, 2, 3}.
Step 10: Search trie for max XOR with xi = 1 (001). Greedy path: bit 2 → go 0 (forced), bit 1 → go 1 (opposite of 0), bit 0 → go 0 (opposite of 1). Reaches element 2 (010). XOR = 1 XOR 2 = 3. ans[1] = 3.
Step 11: Process Query 2: xi = 5, mi = 6. Insert remaining elements ≤ 6.
Step 12: Insert nums[4] = 4 (100). j = 5. All nums inserted. Trie now contains {0, 1, 2, 3, 4}.
Step 13: Search trie for max XOR with xi = 5 (101). Greedy path: bit 2 → go 0 (opposite of 1), bit 1 → go 1 (opposite of 0), bit 0 → go 0 (opposite of 1). Reaches element 2 (010). XOR = 5 XOR 2 = 7. ans[2] = 7.
Step 14: Final answer: [3, 3, 7]. Each element was inserted exactly once. Each query answered in O(3) bit-level steps.
Offline Processing — Incremental Trie Across Three Queries — Watch how the trie grows incrementally as we process queries in ascending order of mi, avoiding any redundant rebuilds.
Algorithm
- Sort nums in ascending order
- Create an array of (original_index, query) pairs and sort by mi
- Initialize an empty binary trie and pointer j = 0
- Initialize result array with -1 for all positions
- For each query (xi, mi) in sorted order:
a. While j < len(nums) and nums[j] ≤ mi:- Insert nums[j] into the trie (31-bit path from MSB to LSB)
- Increment j
b. If the trie is empty (no elements qualified), leave -1
c. Otherwise search the trie for max XOR with xi: - For each bit from 30 down to 0, try the opposite bit of xi; if unavailable, take the same bit
d. Store the result at the original query index
- Return the result array
Code
class Solution {
public:
struct TrieNode {
TrieNode* children[2] = {nullptr, nullptr};
};
void insert(TrieNode* root, int num) {
TrieNode* node = root;
for (int bit = 30; bit >= 0; bit--) {
int b = (num >> bit) & 1;
if (!node->children[b])
node->children[b] = new TrieNode();
node = node->children[b];
}
}
int search(TrieNode* root, int xi) {
if (!root->children[0] && !root->children[1]) return -1;
TrieNode* node = root;
int maxXor = 0;
for (int bit = 30; bit >= 0; bit--) {
int b = (xi >> bit) & 1;
int want = b ^ 1;
if (node->children[want]) {
maxXor |= (1 << bit);
node = node->children[want];
} else {
node = node->children[b];
}
}
return maxXor;
}
vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
sort(nums.begin(), nums.end());
int n = nums.size(), q = queries.size();
vector<int> result(q, -1);
vector<pair<int, int>> sortedQ;
for (int i = 0; i < q; i++)
sortedQ.push_back({queries[i][1], i});
sort(sortedQ.begin(), sortedQ.end());
TrieNode* root = new TrieNode();
int j = 0;
for (auto& [mi, idx] : sortedQ) {
int xi = queries[idx][0];
while (j < n && nums[j] <= mi) {
insert(root, nums[j]);
j++;
}
result[idx] = search(root, xi);
}
return result;
}
};class TrieNode:
def __init__(self):
self.children = [None, None]
class Solution:
def maximizeXor(self, nums: list[int], queries: list[list[int]]) -> list[int]:
nums.sort()
q = len(queries)
result = [-1] * q
root = TrieNode()
j = 0
for idx, (xi, mi) in sorted(enumerate(queries), key=lambda x: x[1][1]):
while j < len(nums) and nums[j] <= mi:
node = root
for bit in range(30, -1, -1):
b = (nums[j] >> bit) & 1
if node.children[b] is None:
node.children[b] = TrieNode()
node = node.children[b]
j += 1
if root.children[0] is None and root.children[1] is None:
continue
node = root
max_xor = 0
for bit in range(30, -1, -1):
b = (xi >> bit) & 1
want = b ^ 1
if node.children[want]:
max_xor |= (1 << bit)
node = node.children[want]
else:
node = node.children[b]
result[idx] = max_xor
return resultclass Solution {
static class TrieNode {
TrieNode[] children = new TrieNode[2];
}
private void insert(TrieNode root, int num) {
TrieNode node = root;
for (int bit = 30; bit >= 0; bit--) {
int b = (num >> bit) & 1;
if (node.children[b] == null)
node.children[b] = new TrieNode();
node = node.children[b];
}
}
private int search(TrieNode root, int xi) {
if (root.children[0] == null && root.children[1] == null) return -1;
TrieNode node = root;
int maxXor = 0;
for (int bit = 30; bit >= 0; bit--) {
int b = (xi >> bit) & 1;
int want = b ^ 1;
if (node.children[want] != null) {
maxXor |= (1 << bit);
node = node.children[want];
} else {
node = node.children[b];
}
}
return maxXor;
}
public int[] maximizeXor(int[] nums, int[][] queries) {
Arrays.sort(nums);
int n = nums.length, q = queries.length;
int[] result = new int[q];
Arrays.fill(result, -1);
int[][] sortedQ = new int[q][3];
for (int i = 0; i < q; i++)
sortedQ[i] = new int[]{queries[i][1], queries[i][0], i};
Arrays.sort(sortedQ, (a, b) -> a[0] - b[0]);
TrieNode root = new TrieNode();
int j = 0;
for (int[] query : sortedQ) {
int mi = query[0], xi = query[1], idx = query[2];
while (j < n && nums[j] <= mi) {
insert(root, nums[j]);
j++;
}
result[idx] = search(root, xi);
}
return result;
}
}Complexity Analysis
Time Complexity: O(n log n + q log q + (n + q) × 31)
Sorting nums costs O(n log n) and sorting queries costs O(q log q). Each of the n elements is inserted into the trie exactly once, taking O(31) per insertion — total O(31n). Each of the q queries requires one trie search at O(31) per search — total O(31q). Since 31 is a constant, the dominant terms are the sorting steps.
Space Complexity: O(31 × n + q)
The trie stores at most n distinct paths, each of depth 31, so the node count is at most 31n. The sorted query array and the result array each use O(q) space. Overall: O(n + q) treating the constant 31 factor as negligible.