Last updated on January 5th, 2025 at 12:59 am

Here, we see the Maximum XOR of Two Numbers in an Array LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Bit-Manipulation, Trie

Companies

Google

Level of Question

Medium

Maximum XOR of Two Numbers in an Array LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The provided code uses the Bitwise XOR with Trie pattern. It involves constructing a binary trie (prefix tree) to efficiently compute the maximum XOR of two numbers in an array.

3. Code Implementation in Different Languages

3.1 Maximum XOR of Two Numbers in an Array C++

class TrieNode{
public:
    TrieNode *child[2];
    TrieNode(){
        this->child[0] = NULL;
        this->child[1] = NULL;
    }
};

class Solution {
    TrieNode *newNode;
    void insert(int x){
        TrieNode *t = newNode;
        bitset<32> bs(x);
        for(int j=31; j>=0; j--){
            if(!t->child[bs[j]]) t->child[bs[j]] = new TrieNode();
            t = t->child[bs[j]];
        }    
    }
public:
    int findMaximumXOR(vector<int>& nums) {
        newNode = new TrieNode();
        for(auto &n : nums) insert(n);
        int ans=0;
        for(auto n : nums){
            ans = max(ans, maxXOR(n));
        }
        return ans;
    }
    int maxXOR(int n){
        TrieNode *t = newNode;
        bitset<32> bs(n);
        int ans=0; 
        for(int j=31; j>=0; j--){
            if(t->child[!bs[j]]) ans += (1<<j), t = t->child[!bs[j]];
            else t = t->child[bs[j]];
        }
        return ans;
    }
};

3.2 Maximum XOR of Two Numbers in an Array Java

class Node {
    HashMap<Integer, Node> children;
    Node() {
        this.children = new HashMap<>();
    }
}

class Trie {
    Node root;
    Trie() {
        this.root = new Node();
    }
    public void insert(int[] A) {
        for(int num : A) {
            Node curr = this.root;
            for(int i=31;i>=0;i--) {
                int currBit = (num >> i) & 1;
                if(!curr.children.containsKey(currBit)) 
                    curr.children.put(currBit, new Node());
                curr = curr.children.get(currBit);
            }
        }
    }
}

class Solution {
    public int findMaximumXOR(int[] nums) {
        Trie trie = new Trie();
        trie.insert(nums);
        int max = 0;
        for(int num : nums) {
            Node curr = trie.root;
            int currSum = 0;
            for(int i=31;i>=0;i--) {
                int requiredBit = 1-((num >> i) & 1);
                if(curr.children.containsKey(requiredBit)) {
                    currSum |= (1<<i);
                    curr = curr.children.get(requiredBit);
                } else {
                    curr = curr.children.get(1-requiredBit);
                }
            }
            max = Math.max(max, currSum);
        }
        return max;
    }
}

3.3 Maximum XOR of Two Numbers in an Array JavaScript

var findMaximumXOR = function(nums) {
  let trie = new Trie();
  let root = trie.root;
  for(let num of nums) {
    trie.insert(num);
  }
  let ans = 0;
  let INTEGER_MAX = Math.pow(2, 31) - 1;
  for(let num of nums) {
    let target = num ^ INTEGER_MAX;
    let found = trie.search(target);
    ans = Math.max(ans, num ^ found);
  }
  return ans;
};

class Trie {
  root = new Map();
  insert(number) {
    let index = 30;
    let node = this.root;
    while(index >= 0) {
      let mask = 1 << index;
      let bit = (number & mask) > 0 ? 1 : 0;
      if(!node.has(bit)) {
        node.set(bit, new Map());
      }
      node = node.get(bit);
      index--;
    }
  }
  search(number) {
    let ans = 0;
    let index = 30;
    let node = this.root;
    while(index >= 0) {
      let mask = 1 << index;
      let bit = (number & mask) > 0 ? 1 : 0;
      if (node.has(bit)) {
        node = node.get(bit);
      } else {
        bit = bit === 0 ? 1 : 0
        node = node.get(bit);
      }
      if (bit === 1) {
        ans = ans + mask;
      }
      index--;
    }
    return ans;
  }
}

3.4 Maximum XOR of Two Numbers in an Array Python

class Solution(object):
    def findMaximumXOR(self, nums):
        m, mask = 0, 0
        for i in range(32)[::-1]:
            mask |= 1 << i
            prefixes = {n & mask for n in nums}
            tmp = m | (1 << i)
            if any(prefix ^ tmp in prefixes for prefix in prefixes):
                m = tmp
        return m

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(N)	O(N)
Java	O(N)	O(N)
JavaScript	O(N)	O(N)
Python	O(N)	O(N)