Problem

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 arrayanswer whereanswer.length == queries.length andanswer[i]is the answer to theith query.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    
    
    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

1
2
3
4
5
6


    
    
    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 <= 10^5
  • queries[i].length == 2
  • 0 <= nums[j], xi, mi <= 10^9

Solution

Method 1 – Offline Queries with Trie

Intuition

To efficiently answer each query, we need to quickly find the maximum XOR of xi with any nums[j] not exceeding mi. A Trie (prefix tree) can help us find the best XOR match for each query. By sorting both nums and queries by mi, we can insert eligible nums[j] into the Trie as we process each query.

Approach

  1. Sort nums in ascending order.
  2. For each query, sort queries by mi and keep track of their original indices.
  3. Use a Trie to insert numbers from nums that are <= mi for the current query.
  4. For each query, if Trie is not empty, find the maximum XOR of xi with any number in Trie; else, answer is -1.
  5. Restore answers to the original query order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Trie {
    Trie* child[2] = {};
public:
    void insert(int num) {
        Trie* node = this;
        for (int i = 30; i >= 0; --i) {
            int b = (num >> i) & 1;
            if (!node->child[b]) node->child[b] = new Trie();
            node = node->child[b];
        }
    }
    int getMaxXor(int num) {
        Trie* node = this;
        int ans = 0;
        for (int i = 30; i >= 0; --i) {
            int b = (num >> i) & 1;
            if (node->child[1 - b]) {
                ans |= (1 << i);
                node = node->child[1 - b];
            } else if (node->child[b]) {
                node = node->child[b];
            } else {
                return -1;
            }
        }
        return ans;
    }
};
class Solution {
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        sort(nums.begin(), nums.end());
        vector<pair<int, pair<int, int>>> q;
        for (int i = 0; i < queries.size(); ++i)
            q.push_back({queries[i][1], {queries[i][0], i}});
        sort(q.begin(), q.end());
        vector<int> ans(queries.size(), -1);
        Trie trie;
        int idx = 0;
        for (auto& [mi, p] : q) {
            int xi = p.first, i = p.second;
            while (idx < nums.size() && nums[idx] <= mi) trie.insert(nums[idx++]);
            if (idx) ans[i] = trie.getMaxXor(xi);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

type Trie struct {
    child [2]*Trie
}
func (t *Trie) insert(num int) {
    node := t
    for i := 30; i >= 0; i-- {
        b := (num >> i) & 1
        if node.child[b] == nil {
            node.child[b] = &Trie{}
        }
        node = node.child[b]
    }
}
func (t *Trie) getMaxXor(num int) int {
    node := t
    ans := 0
    for i := 30; i >= 0; i-- {
        b := (num >> i) & 1
        if node.child[1-b] != nil {
            ans |= 1 << i
            node = node.child[1-b]
        } else if node.child[b] != nil {
            node = node.child[b]
        } else {
            return -1
        }
    }
    return ans
}
func maximizeXor(nums []int, queries [][]int) []int {
    sort.Ints(nums)
    type Q struct{ mi, xi, idx int }
    q := make([]Q, len(queries))
    for i, v := range queries {
        q[i] = Q{v[1], v[0], i}
    }
    sort.Slice(q, func(i, j int) bool { return q[i].mi < q[j].mi })
    ans := make([]int, len(queries))
    trie := &Trie{}
    idx := 0
    for _, v := range q {
        for idx < len(nums) && nums[idx] <= v.mi {
            trie.insert(nums[idx])
            idx++
        }
        if idx > 0 {
            ans[v.idx] = trie.getMaxXor(v.xi)
        } else {
            ans[v.idx] = -1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Trie {
    Trie[] child = new Trie[2];
}
class Solution {
    public int[] maximizeXor(int[] nums, int[][] queries) {
        Arrays.sort(nums);
        int n = queries.length;
        int[][] q = new int[n][3];
        for (int i = 0; i < n; i++) {
            q[i][0] = queries[i][1];
            q[i][1] = queries[i][0];
            q[i][2] = i;
        }
        Arrays.sort(q, Comparator.comparingInt(a -> a[0]));
        int[] ans = new int[n];
        Trie trie = new Trie();
        int idx = 0;
        for (int[] v : q) {
            int mi = v[0], xi = v[1], i = v[2];
            while (idx < nums.length && nums[idx] <= mi) {
                Trie node = trie;
                for (int k = 30; k >= 0; k--) {
                    int b = (nums[idx] >> k) & 1;
                    if (node.child[b] == null) node.child[b] = new Trie();
                    node = node.child[b];
                }
                idx++;
            }
            if (idx > 0) {
                Trie node = trie;
                int res = 0;
                for (int k = 30; k >= 0; k--) {
                    int b = (xi >> k) & 1;
                    if (node.child[1 - b] != null) {
                        res |= (1 << k);
                        node = node.child[1 - b];
                    } else if (node.child[b] != null) {
                        node = node.child[b];
                    } else {
                        res = -1;
                        break;
                    }
                }
                ans[i] = res;
            } else {
                ans[i] = -1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Trie {
    val child = arrayOfNulls<Trie>(2)
}
class Solution {
    fun maximizeXor(nums: IntArray, queries: Array<IntArray>): IntArray {
        nums.sort()
        val n = queries.size
        val q = Array(n) { IntArray(3) }
        for (i in 0 until n) {
            q[i][0] = queries[i][1]
            q[i][1] = queries[i][0]
            q[i][2] = i
        }
        q.sortBy { it[0] }
        val ans = IntArray(n)
        val trie = Trie()
        var idx = 0
        for (v in q) {
            val mi = v[0]; val xi = v[1]; val i = v[2]
            while (idx < nums.size && nums[idx] <= mi) {
                var node = trie
                for (k in 30 downTo 0) {
                    val b = (nums[idx] shr k) and 1
                    if (node.child[b] == null) node.child[b] = Trie()
                    node = node.child[b]!!
                }
                idx++
            }
            if (idx > 0) {
                var node = trie
                var res = 0
                for (k in 30 downTo 0) {
                    val b = (xi shr k) and 1
                    if (node.child[1 - b] != null) {
                        res = res or (1 shl k)
                        node = node.child[1 - b]!!
                    } else if (node.child[b] != null) {
                        node = node.child[b]!!
                    } else {
                        res = -1
                        break
                    }
                }
                ans[i] = res
            } else {
                ans[i] = -1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

def maximize_xor(nums: list[int], queries: list[list[int]]) -> list[int]:
    class Trie:
        def __init__(self):
            self.child = [None, None]
    def insert(root: Trie, num: int):
        node = root
        for i in range(30, -1, -1):
            b = (num >> i) & 1
            if not node.child[b]:
                node.child[b] = Trie()
            node = node.child[b]
    def get_max_xor(root: Trie, num: int) -> int:
        node = root
        ans = 0
        for i in range(30, -1, -1):
            b = (num >> i) & 1
            if node.child[1 - b]:
                ans |= (1 << i)
                node = node.child[1 - b]
            elif node.child[b]:
                node = node.child[b]
            else:
                return -1
        return ans
    nums.sort()
    q = sorted([(mi, xi, i) for i, (xi, mi) in enumerate(queries)])
    ans = [-1] * len(queries)
    root = Trie()
    idx = 0
    for mi, xi, i in q:
        while idx < len(nums) and nums[idx] <= mi:
            insert(root, nums[idx])
            idx += 1
        if idx:
            ans[i] = get_max_xor(root, xi)
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

struct Trie { child: [Option<Box<Trie>>; 2] }
impl Trie {
    fn new() -> Self { Trie { child: [None, None] } }
    fn insert(&mut self, num: i32) {
        let mut node = self;
        for i in (0..=30).rev() {
            let b = (num >> i) & 1;
            node = node.child[b as usize].get_or_insert_with(|| Box::new(Trie::new()));
        }
    }
    fn get_max_xor(&self, num: i32) -> i32 {
        let mut node = self;
        let mut ans = 0;
        for i in (0..=30).rev() {
            let b = (num >> i) & 1;
            if let Some(ref next) = node.child[(1 - b) as usize] {
                ans |= 1 << i;
                node = next;
            } else if let Some(ref next) = node.child[b as usize] {
                node = next;
            } else {
                return -1;
            }
        }
        ans
    }
}
impl Solution {
    pub fn maximize_xor(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let mut nums = nums;
        nums.sort();
        let mut q: Vec<(i32, i32, usize)> = queries.iter().enumerate().map(|(i, v)| (v[1], v[0], i)).collect();
        q.sort();
        let mut ans = vec![-1; queries.len()];
        let mut trie = Trie::new();
        let mut idx = 0;
        for (mi, xi, i) in q {
            while idx < nums.len() && nums[idx] <= mi {
                trie.insert(nums[idx]);
                idx += 1;
            }
            if idx > 0 {
                ans[i] = trie.get_max_xor(xi);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Trie {
    child: [Trie?, Trie?] = [undefined, undefined];
}
class Solution {
    maximizeXor(nums: number[], queries: number[][]): number[] {
        nums.sort((a, b) => a - b);
        const q = queries.map(([xi, mi], i) => [mi, xi, i]).sort((a, b) => a[0] - b[0]);
        const ans = Array(queries.length).fill(-1);
        const root = new Trie();
        let idx = 0;
        function insert(num: number) {
            let node = root;
            for (let i = 30; i >= 0; --i) {
                const b = (num >> i) & 1;
                if (!node.child[b]) node.child[b] = new Trie();
                node = node.child[b]!;
            }
        }
        function getMaxXor(num: number): number {
            let node = root, ans = 0;
            for (let i = 30; i >= 0; --i) {
                const b = (num >> i) & 1;
                if (node.child[1 - b]) {
                    ans |= (1 << i);
                    node = node.child[1 - b]!;
                } else if (node.child[b]) {
                    node = node.child[b]!;
                } else {
                    return -1;
                }
            }
            return ans;
        }
        for (const [mi, xi, i] of q) {
            while (idx < nums.length && nums[idx] <= mi) insert(nums[idx++]);
            if (idx) ans[i] = getMaxXor(xi);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O((n + q) * 31), where n is the length of nums and q is the number of queries. Each insert and query takes up to 31 steps for 32-bit numbers.
  • 🧺 Space complexity: O(n * 31), for the Trie storing up to n numbers.