Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• RenderScript

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

• 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)
  
  

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

All Problems

All Solutions