Max XOR of Two Numbers in an Array

// Brute Force Approach for finding the maximum XOR
// value from all the pairs in an array
public class Solution{

    // Method to find the maximum XOR value 
    static int maxXOR(int[] arr, int size)
    {
        int maximumXOR = 0;

        // Iterate over all the pairs of an array
        for(int i = 0; i < size; i++)
        {
            // This will hold the value of the XOR of the element arr[i] and arr[j]
            int currentXOR = 0;  
            for(int j = i + 1; j < size; j++)
            {
                currentXOR = arr[i] ^ arr[j];
                maximumXOR = Math.max(maximumXOR, currentXOR);
            }
        }

        return maximumXOR;
    }
    public static void main(String[] args) {
        int[] arr = {3,10,5,25,2,8};
        System.out.println("Maximum XOR value from arr is: ");
        System.out.println(maxXOR(arr, arr.length));

        int[] arr2 = {14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70};
        System.out.println("Maximum XOR value from arr2 is: ");
        System.out.println(maxXOR(arr2, arr2.length));
        
    }
}

You can also try this code with Online Java Compiler

Run Code

#include <bits/stdc++.h>
using namespace std;


int max_xor(int arr[], int n)
{


int maxXor = 0;


// Calculating xor of each pair
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
maxXor = max(maxXor,
arr[i] ^ arr[j]);
}
}
return maxXor;
}
int main()
{


int arr[] = {3,10,5,25,2,8};
int n = sizeof(arr) / sizeof(arr[0]);


cout << "Maximum XOR value in the array is: "<<max_xor(arr, n) << endl;
return 0;
}

You can also try this code with Online C++ Compiler

Run Code

from typing import List


def findMaximumXOR(self, nums: List[int]) -> int:
    result = 0
    for i in range(0, len(arr)):
        for j in range(1, len(arr)):
            calc = arr[i] ^ arr[j]
            result = max(result, calc)

    return result


arr = [14, 70, 53, 33, 49, 91, 36, 80, 92, 51, 66, 70]
print(findMaximumXOR(arr, arr))

You can also try this code with Online Python Compiler

Run Code

import java.util.HashSet;
import java.util.Set;
class MaximumXOR{

    public static int findMaximum(int[] arr){

        // The first step is to find the maximum number in
        // the array. Because we will take the number
        // of bits which are there in the binary 
        // representation of the maximum number

        // Finding the maximum number of the array
        int maxNum = arr[0];
        for(int i = 0; i < arr.length; i++){
            maxNum = Math.max(maxNum, arr[i]);
        }

        // Finding the number of bits in the maximum
        // number
        int maxBits = (Integer.toBinaryString(maxNum)).length();

        int maxXOR = 0;
        int currXOR;

        Set<Integer> prefix = new HashSet<>();

        // Step 2: Iterate over the bits of the number
        for(int i = maxBits - 1; i > -1; --i){

            // Left Shift maxXOR by 1 bit so that the next bit 
            // can be reached
            maxXOR <<= 1;

            // Set 1 in the smallest bit
            currXOR = maxXOR | 1;

            prefix.clear();

            // compute all possible prefixes of length maxBits - 1
            // in binary representation
            for(int num : arr){
                prefix.add(num >> i);
            }

            // Update the maxXOR, if any two of the prefixes
            // could result in currXOR

            for(int j: prefix){
                if(prefix.contains(currXOR^j)){
                    maxXOR = currXOR;
                    break;
                }
            }
        }
        return maxXOR;
    }
    public static void main(String[]args){
        int[] nums = {3, 10, 5, 15, 2, 8};
        System.out.println("Maximum XOR value in the array, arr is");
        System.out.println(findMaximum(nums));
    }
}

You can also try this code with Online Java Compiler

Run Code

#include <bits/stdc++.h>
using namespace std;


int FindMaxXor(int arr[], int n)
{
int maxx = 0, mask = 0;


set<int> s;


for (int i = 30; i >= 0; i--) 
    {


// setting the i'th bit in mask
mask |= (1 << i);


for (int i = 0; i < n; ++i) {


s.insert(arr[i] & mask);
}


int newMaxx = maxx | (1 << i);


for (int prefix:s) {


if (s.count(newMaxx ^ prefix)) {
maxx = newMaxx;
break;
}
}
        s.clear();
}


return maxx;
}


// Driver Code
int main()
{


int arr[] = {3, 10, 5, 15, 2, 8};
int n = sizeof(arr) / sizeof(arr[0]);


cout << "Maximum XOR value in the array is: "<<FindMaxXor(arr, n) << endl;


return 0;
}

You can also try this code with Online C++ Compiler

Run Code

from typing import List
"""
           let ni and nj be the numbers such that xor between them produces maximum
           value among other pairs. let m be the max value.

           m = ni ^ nj
           => m ^ nj = (ni ^ nj) ^ nj
           =>        = ni ^ (nj ^ nj) # xor is associative
           =>        = ni ^ 0
           =>        = ni

           so, m ^ nj = ni

           We note that m is 31-bit integer so we guess bits of m and and with each nj,
           we check if the combination of m and nj will produce ni.

           So time complexity becomes O(32N) = O(N)
           :param nums:
           :return:
           """


def findMaximumXOR(self, nums: List[int]) -> int:
    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


arr = [3, 10, 5, 25, 2, 8]
print(findMaximumXOR(arr, arr))

You can also try this code with Online Python Compiler

Run Code

class XorUsingTrie {
    static class Node {
        Node left;
        Node right;
    };

    // A utility method to insert the 32 bit binary representation of a number
    // x in the trie.
    static void insertTrie(int x, Node head) {

        Node curr = head;

        for (int i = 30; i >= 0; i--) {
            // Finding the bit at the ith position
            int val = (x >> i) & 1;

            // if the current bit is 0, it will be stored to
            // the left of curr node.
            if (val == 0) {

                // if the curr.left is null
                if (curr.left == null) {
                    curr.left = new Node();
                }

                curr = curr.left;
            }

            // if the bit at the ith position is 1, it will
            // be stored to the right of the curr node.
            else {
                // If the curr.right is null
                if (curr.right == null) {
                    curr.right = new Node();
                }

                curr = curr.right;
            }
        }
    }

    // Function to find the maximum XOR value amongst
    // all the pairs formed in an array, arr[].
    static int findMaximum(int[] arr, int size) {

        // Head node of the trie data structure.
        Node head = new Node();

        // Step 1: Insert each element to the trie
        for (int i = 0; i < size; i++) {
            insertTrie(arr[i], head);
        }

        // Step 2: A variable to store the maximum XOR value
        int maximumXOR = 0;

        // Step 3: Traverse the given array, find the ith bit
        // and update the value of the currentXOR.

        for (int i = 0; i < size; i++) {
            int currentXOR = 0;
            // Note that M is 1073741824
            // The decimal representation of M is
            // 1000000000000000000000000000000
            int M = (int)Math.pow(2, 30);

            Node curr = head;
            for (int j = 30; j >= 0; j--) {
                
                // Finding the ith bit
                int val = (arr[i] >> j) & 1;

                // if the ith bit is 0
                if (val == 0) {
                    if (curr.right != null) {
                        currentXOR = currentXOR + M;
                        curr = curr.right;
                    } 
                    
                    else {
                        curr = curr.left;
                    }
                }

                // if the ith bit is 1
                else{
                    if(curr.left != null){
                        currentXOR += M;
                        curr = curr.left;
                    }

                    else{
                        curr = curr.right;
                    }
                }

                // Update the value of M to M/2 to find
                // the next set bit
                M = M/2;
            }

            maximumXOR = Math.max(maximumXOR, currentXOR);
        }
        return maximumXOR;
    }

    public static void main(String[] args) {
       int[] nums = {3, 10, 5, 15, 2, 8};
       System.out.println("Maximum XOR value from nums is: ");
       System.out.println(findMaximum(nums, nums.length)); 
  
     
       int[] arr = {14, 70, 53, 33, 49, 91, 36, 80, 92, 51, 66, 70};
       System.out.println("Maximum XOR value from arr is: ");
       System.out.println(findMaximum(arr, arr.length));
 
    }
}

You can also try this code with Online Java Compiler

Run Code

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
Node* left; // 0
Node* right; // 1

};

class Solution {
public:
Node* root;

Solution() {
root = new Node();
}

void insert(int n) {

Node* temp = root;

for (int i = 31; i >= 0; i--) {
int currentBit = (n >> i) & 1;

if (!currentBit) {
if (!temp->left) temp->left = new Node();
temp = temp->left;
}

else {
if (!temp->right) temp->right = new Node();
temp = temp->right;
}

}
}
    
    
    // O(1) loop
int helper(int val) {
int ans = 0;
Node* temp = root;

// 0 -> move right; else vice versa
for (int i = 31; i >= 0; i--) {
int currentBit = (val >> i) & 1;

if (!currentBit) {
if (temp->right) {
temp = temp->right;
ans += (1 << i);
}
else temp = temp->left;

}
else {
if (temp->left) {
temp = temp->left;
ans += (1 << i);
}
else temp = temp->right;

}

}

return ans;

}

    // O(n)
int findMaximumXOR(vector<int> &arr) {
    int n = arr.size();
int res = 0;
for (int i = 0; i < n; i++) {

int value = arr[i];
insert(value);

int curAns = helper(value);

res = max(curAns, res);
}

return res;
}
};

int main()
{
    int arr[] = {14, 70, 53, 33, 49, 91, 36, 80, 92, 51, 66, 70};
    int n = sizeof(arr) / sizeof(arr[0]);
    Solution s;
    
    vector<int> v(arr, arr + n);
    cout << s.findMaximumXOR(v);
 
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

from typing import List
from collections import defaultdict


class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.val = 0


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, binary):
        cur = self.root
        for char in binary:
            cur = cur.children[int(char)]

    def search(self, binary) -> int:
        result = 0
        cur = self.root
        for char in binary:
            opposite = 1 - int(char)
            if opposite in cur.children:
                result = (result << 1) | 1
                cur = cur.children[opposite]
            else:
                result = (result << 1)
                cur = cur.children[int(char)]
        return result


def findMaximumXOR(self, nums: List[int]) -> int:
    trie = Trie()
    result = float('-inf')
    # format binary string in length of  max num
    maxLen = len(bin(max(nums))[2:])
    for num in nums:
        key = bin(num)[2:].zfill(maxLen)
        trie.insert(key)
        result = max(result, trie.search(key))
    return result


arr = [14, 70, 53, 33, 49, 91, 36, 80, 92, 51, 66, 70]
print(findMaximumXOR(arr, arr))

You can also try this code with Online Python Compiler

Run Code