Last updated on October 5th, 2024 at 04:48 pm

Here, We see Maximum XOR of Two Numbers in an Array LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Maximum XOR of Two Numbers in an Array LeetCode Solution

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

1. Maximum XOR of Two Numbers in an Array LeetCode Solution 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;
    }
};

2. Maximum XOR of Two Numbers in an Array LeetCode Solution 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. Maximum XOR of Two Numbers in an Array Solution 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;
  }
}

4. Maximum XOR of Two Numbers in an Array Solution 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