Maximum XOR With an Element From Array
Solve this Problem
You're given an array
nums and a batch of queries, each one a pair [x, m]. For every query, find the largest XOR that x can produce against any value in nums that doesn't exceed the limit m — and if nothing in nums qualifies, the answer for that query is -1.
Answering each query by rescanning the array works, but every query's eligible set is really just a growing subset of nums as the limit increases. Sorting the queries by their limit and sorting nums once turns this into a single sweep: insert values into the answer structure only as they become eligible, and each query gets answered against everything inserted so far — no value ever needs to be considered by two different rescans.
Test Case 1:
Input:nums = [0, 1, 2, 3, 4], queries = [[3, 1], [1, 3], [5, 6]]
Output:[3, 3, 7]
Explanation:Query [3,1]: only 0 and 1 qualify, best is 3^0=3. Query [1,3]: 0..3 qualify, best is 1^2=3. Query [5,6]: everything qualifies, best is 5^2=7.
Test Case 2:
Input:nums = [5, 2, 4, 6, 6, 3], queries = [[12, 4], [8, 1], [6, 3]]
Output:[15, -1, 5]
Explanation:Query [8,1]: nothing in nums is ≤1, so the answer is -1.
Test Case 3:
Input:nums = [1], queries = [[1, 0]]
Output:[-1]
Explanation:The only value, 1, exceeds the limit 0 — no eligible candidate.
Constraints
- ◆
1 ≤ nums.length ≤ 10⁴ - ◆
1 ≤ queries.length ≤ 10⁴ - ◆
0 ≤ nums[i] ≤ 10⁹ - ◆
0 ≤ x ≤ 10⁹ and 0 ≤ m ≤ 10⁹ for every query [x, m] - ◆
If no value in nums is ≤ m, the answer for that query is -1
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Rescan for Every Query
BruteFor every query, scan the whole array and keep the best XOR among values that don't exceed the query's limit; report -1 if nothing qualifies. Straightforward, but with many queries this rescans the same eligible values over and over.
Time
O(q × n)Space
O(1) extraJava
1class Solution {
2 public int[] maximumXorQueries(int[] nums, int[][] queries) {
3 int[] answers = new int[queries.length];
4 for (int i = 0; i < queries.length; i++) {
5 int x = queries[i][0];
6 int m = queries[i][1];
7 int best = -1;
8 for (int num : nums) {
9 if (num <= m) {
10 best = Math.max(best, x ^ num);
11 }
12 }
13 answers[i] = best;
14 }
15 return answers;
16 }
17}Optimal — Sort Queries + Offline Bitwise Trie
OptimalSort the queries by their limit, smallest first, and sort the array once too. Walk through the sorted array and the sorted queries together — insert every value into a bitwise trie as it becomes eligible (never removing anything, since eligibility only grows as the limit increases), and answer each query by walking the trie bit by bit, always preferring the branch that disagrees with the query value's current bit. Every value is inserted exactly once across the whole run, no matter how many queries end up seeing it.
Time
O((n + q) log n)Space
O(n)Java
1class Solution {
2 private static final int HIGH_BIT = 29;
3 private int[][] children;
4 private int nodeCount;
5
6 public int[] maximumXorQueries(int[] nums, int[][] queries) {
7 int n = nums.length;
8 int q = queries.length;
9 int[] sortedNums = nums.clone();
10 Arrays.sort(sortedNums);
11
12 Integer[] order = new Integer[q];
13 for (int i = 0; i < q; i++) order[i] = i;
14 Arrays.sort(order, (a, b) -> queries[a][1] - queries[b][1]);
15
16 children = new int[n * (HIGH_BIT + 1) + 1][2];
17 for (int[] row : children) {
18 row[0] = -1;
19 row[1] = -1;
20 }
21 nodeCount = 1;
22
23 int[] answers = new int[q];
24 Arrays.fill(answers, -1);
25
26 int j = 0;
27 int inserted = 0;
28 for (int idx : order) {
29 int m = queries[idx][1];
30 while (j < n && sortedNums[j] <= m) {
31 insert(sortedNums[j]);
32 j++;
33 inserted++;
34 }
35 if (inserted > 0) {
36 answers[idx] = queryMax(queries[idx][0]);
37 }
38 }
39 return answers;
40 }
41
42 private void insert(int num) {
43 int node = 0;
44 for (int bit = HIGH_BIT; bit >= 0; bit--) {
45 int b = (num >> bit) & 1;
46 if (children[node][b] == -1) {
47 children[node][b] = nodeCount++;
48 }
49 node = children[node][b];
50 }
51 }
52
53 private int queryMax(int x) {
54 int node = 0;
55 int result = 0;
56 for (int bit = HIGH_BIT; bit >= 0; bit--) {
57 int b = (x >> bit) & 1;
58 int want = 1 - b;
59 if (children[node][want] != -1) {
60 result |= (1 << bit);
61 node = children[node][want];
62 } else {
63 node = children[node][b];
64 }
65 }
66 return result;
67 }
68}