Leetcode 1707. Maximum XOR With an Element From Array

Problem Description

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 i-th 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.

You need to return an integer array answer where answer.length == queries.length and answer[i] is the answer to the i-th query.

Example

For example, given nums = [0,1,2,3,4] and queries = [[3,1],[1,3],[5,6]], the output should be [3,3,7].

Let's walk through each query:

1. For query queries[0] = [3,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. For query queries[1] = [1,3], 1 XOR 2 = 3.
3. For query queries[2] = [5,6], 5 XOR 2 = 7.

Solution Approach

In this problem, we will use a Trie data structure to solve this problem. A Trie, or a prefix tree, is an efficient way to store information about strings or sequences, which allows searching for prefixes very quickly. In this case, we will store binary representation of the numbers in the Trie. Each node of the Trie can have two children - one representing a 0 bit and one representing a 1 bit.

We will start by building a Trie from the given nums array. Then, for each query [xi, mi], we will traverse the Trie in such a way that we maximize the XOR value while making sure that the current number does not exceed mi. This can be done by traversing the Trie from left to right while making decision at each level to go left or right, based on the current bit of xi and mi.

Let's implement the solution below.

Python Solution

1class Trie:
2    def __init__(self):
3        self.children = [None] * 2
4        
5    def insert(self, num):
6        node = self
7        for i in range(31, -1, -1):
8            bit = (num >> i) & 1
9            if not node.children[bit]:
10                node.children[bit] = Trie()
11            node = node.children[bit]
12            
13    def max_xor(self, xi, mi):
14        node = self
15        num = 0
16        for i in range(31, -1, -1):
17            xi_bit = (xi >> i) & 1
18            mi_bit = (mi >> i) & 1
19            if mi_bit == 1:
20                bit = 1 - xi_bit if node.children[1 - xi_bit] else xi_bit
21            else:
22                bit = xi_bit
23            if not node.children[bit]:
24                return -1
25            num = (num << 1) | bit
26            node = node.children[bit]
27        return num ^ xi
28        
29        
30class Solution:
31    def maximizeXor(self, nums, queries):
32        root = Trie()
33        
34        for num in nums:
35            root.insert(num)
36            
37        answer = []
38        for xi, mi in queries:
39            answer.append(root.max_xor(xi, mi))
40            
41        return answer

Java Solution

1class Trie {
2    Trie[] children = new Trie[2];
3
4    void insert(int num) {
5        Trie node = this;
6        for (int i = 31; i >= 0; i--) {
7            int bit = (num >> i) & 1;
8            if (node.children[bit] == null) {
9                node.children[bit] = new Trie();
10            }
11            node = node.children[bit];
12        }
13    }
14
15    int max_xor(int xi, int mi) {
16        Trie node = this;
17        int num = 0;
18        for (int i = 31; i >= 0; i--) {
19            int xi_bit = (xi >> i) & 1;
20            int mi_bit = (mi >> i) & 1;
21            int bit = mi_bit == 1 ? (node.children[1 - xi_bit] != null ? 1 - xi_bit : xi_bit) : xi_bit;
22            if (node.children[bit] == null) {
23                return -1;
24            }
25            num = (num << 1) | bit;
26            node = node.children[bit];
27        }
28        return num ^ xi;
29    }
30}
31
32class Solution {
33    public int[] maximizeXor(int[] nums, int[][] queries) {
34        Trie root = new Trie();
35
36        for (int num : nums) {
37            root.insert(num);
38        }
39
40        int[] answer = new int[queries.length];
41        for (int i = 0; i < queries.length; i++) {
42            int xi = queries[i][0];
43            int mi = queries[i][1];
44            answer[i] = root.max_xor(xi, mi);
45        }
46
47        return answer;
48    }
49}

JavaScript Solution

1class Trie {
2    constructor() {
3        this.children = [null, null];
4    }
5
6    insert(num) {
7        let node = this;
8        for (let i = 31; i >= 0; i--) {
9            let bit = (num >> i) & 1;
10            if (!node.children[bit]) {
11                node.children[bit] = new Trie();
12            }
13            node = node.children[bit];
14        }
15    }
16
17    max_xor(xi, mi) {
18        let node = this;
19        let num = 0;
20        for (let i = 31; i >= 0; i--) {
21            let xi_bit = (xi >> i) & 1;
22            let mi_bit = (mi >> i) & 1;
23            let bit = mi_bit === 1 ? (node.children[1 - xi_bit] ? 1 - xi_bit : xi_bit) : xi_bit;
24            if (!node.children[bit]) {
25                return -1;
26            }
27            num = (num << 1) | bit;
28            node = node.children[bit];
29        }
30        return num ^ xi;
31    }
32}
33
34function maximizeXor(nums, queries) {
35    const root = new Trie();
36
37    for (const num of nums) {
38        root.insert(num);
39    }
40
41    const answer = [];
42    for (const [xi, mi] of queries) {
43        answer.push(root.max_xor(xi, mi));
44    }
45
46    return answer;
47}

Conclusion

In this post, we have discussed a problem where we need to find the maximum bitwise XOR value for each query. We have seen how to use a Trie data structure to solve this problem efficiently. Trie allows us to insert binary representation of the numbers and then find the maximum bitwise XOR value, while also considering the constraint that the current number should not exceed the given value. We have implemented the solution in Python, Java, and JavaScript.