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
PythonJavaC++GoRust
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)(code-box)
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;
}
}(code-box)
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; --i) {
int 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 {
public:
int findMaximumXOR(vector<int>& nums) {
Trie* trie = new Trie();
int ans = 0;
for (int x : nums) {
trie->insert(x);
ans = max(ans, trie->search(x));
}
return ans;
}
};(code-box)
type Trie struct {
children [2]*Trie
}
func newTrie() *Trie {
return &Trie{}
}
func (t *Trie) insert(x int) {
node := t
for i := 30; i >= 0; i-- {
v := x >> i & 1
if node.children[v] == nil {
node.children[v] = newTrie()
}
node = node.children[v]
}
}
func (t *Trie) search(x int) int {
node := t
ans := 0
for i := 30; i >= 0; i-- {
v := x >> i & 1
if node.children[v^1] != nil {
ans |= 1 << i
node = node.children[v^1]
} else {
node = node.children[v]
}
}
return ans
}
func findMaximumXOR(nums []int) (ans int) {
trie := newTrie()
for _, x := range nums {
trie.insert(x)
ans = max(ans, trie.search(x))
}
return ans
}(code-box)
struct Trie {
children: [Option<Box<Trie>>; 2],
}
impl Trie {
fn new() -> Trie {
Trie {
children: [None, None],
}
}
fn insert(&mut self, x: i32) {
let mut node = self;
for i in (0..=30).rev() {
let v = ((x >> i) & 1) as usize;
if node.children[v].is_none() {
node.children[v] = Some(Box::new(Trie::new()));
}
node = node.children[v].as_mut().unwrap();
}
}
fn search(&self, x: i32) -> i32 {
let mut node = self;
let mut ans = 0;
for i in (0..=30).rev() {
let v = ((x >> i) & 1) as usize;
if let Some(child) = &node.children[v ^ 1] {
ans |= 1 << i;
node = child.as_ref();
} else {
node = node.children[v].as_ref().unwrap();
}
}
ans
}
}
impl Solution {
pub fn find_maximum_xor(nums: Vec<i32>) -> i32 {
let mut trie = Trie::new();
let mut ans = 0;
for &x in nums.iter() {
trie.insert(x);
ans = ans.max(trie.search(x));
}
ans
}
}(code-box)
