Description
Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.
Example 1:
Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.
Example 2:
Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127
Constraints:
1 <= nums.length <= 2 * 1050 <= nums[i] <= 231 - 1
Solutions
Solution 1
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 | class Trie:
__slots__ = ("children",)
def __init__(self):
self.children: List[Trie | None] = [None, None]
def insert(self, x: int):
node = self
for i in range(30, -1, -1):
v = x >> i & 1
if node.children[v] is None:
node.children[v] = Trie()
node = node.children[v]
def search(self, x: int) -> int:
node = self
ans = 0
for i in range(30, -1, -1):
v = x >> i & 1
if node.children[v ^ 1]:
ans |= 1 << i
node = node.children[v ^ 1]
else:
node = node.children[v]
return ans
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
trie = Trie()
for x in nums:
trie.insert(x)
return max(trie.search(x) for x in nums)
|
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 | class Trie {
private Trie[] children = new Trie[2];
public Trie() {
}
public void insert(int x) {
Trie node = this;
for (int i = 30; i >= 0; --i) {
int v = x >> i & 1;
if (node.children[v] == null) {
node.children[v] = new Trie();
}
node = node.children[v];
}
}
public int search(int x) {
Trie node = this;
int ans = 0;
for (int i = 30; i >= 0; --i) {
int v = x >> i & 1;
if (node.children[v ^ 1] != null) {
ans |= 1 << i;
node = node.children[v ^ 1];
} else {
node = node.children[v];
}
}
return ans;
}
}
class Solution {
public int findMaximumXOR(int[] nums) {
Trie trie = new Trie();
int ans = 0;
for (int x : nums) {
trie.insert(x);
ans = Math.max(ans, trie.search(x));
}
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 | class Trie {
public:
Trie* children[2];
Trie()
: children{nullptr, nullptr} {}
void insert(int x) {
Trie* node = this;
for (int i = 30; ~i; --i) {
int v = x >> i & 1;
if (!node->children[v]) {
node->children[v] = new Trie();
}
node = node->children[v];
}
}
int search(int x) {
Trie* node = this;
int ans = 0;
for (int i = 30; ~i
|