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:
- For query
queries[0] = [3,1]
,0
and1
are the only two integers not greater than1
.0 XOR 3 = 3
and1 XOR 3 = 2
. The larger of the two is3
. - For query
queries[1] = [1,3]
,1 XOR 2 = 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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.