Question

421. Maximum XOR of Two Numbers in an Array

中文文档

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 * 105
• 0 <= nums[i] <= 231 - 1

Solutions

Solution 1

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)

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;
  }
}

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;
  }
};

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
}

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
  }
}