Maximum XOR of two numbers in an array

Intuition

XOR, or exclusive OR, is a binary bitwise operation that outputs true (1) only when the input bits differ. If the input bits are the same, the result is 0. If they are different, the result is 1.

Here's the truth table for XOR:

Input1	Input2	Output
0	0	0
0	1	1
1	0	1
1	1	0

The objective is to maximize the XOR result between two numbers. This is achieved by ensuring that for each bit position, the XOR result is maximized. Therefore, we aim to maximize the number of opposite bits between the numbers. To achieve this, we use a Trie data structure. The Trie allows us to traverse each bit of the numbers in the array and maximize the XOR value by selecting the opposite bit when available, ensuring the highest possible XOR result.

Approach

Create a Trie Node Structure: This structure represents a node in the Trie. It contains an array to store links to child nodes (0 and 1) and provides methods to interact with these child nodes, such as checking if a node exists, retrieving it, and adding a new one.
Insert Bit Values into the Trie: Iterate through the given array and insert the bit values of each number into the Trie from left to right. For each number, if the current node does not have a child node for the current bit, create a new child node. Move to the corresponding child node for the current bit.
Initialize Maximum XOR Value: Start from the root node and set the maximum XOR value to 0.
Maximize XOR for Each Number: For each bit of the number, from left to right, check if the opposite bit exists in the Trie. If it does, update the maximum XOR value and move to the child node for the opposite bit. If the opposite bit does not exist, move to the child node for the current bit.
Return the Result: After processing all bits of all numbers, return the maximum XOR value obtained.

Dry Run

For detailed dry run watch the video.

Solution

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

// Node structure for the Trie
struct Node {
    Node* links[2]; 
    
    /*To check if a specific bit 
    key is present in the child nodes*/
    bool containsKey(int bit) {
        return (links[bit] != NULL);
    }
    
    /*To get child node 
    corresponding to a 
    specific bit*/
    Node* get(int bit) {
        return links[bit];
    }
    
    /*To set a child node at a specific 
    index in the links array*/
    void put(int bit, Node* node) {
        links[bit] = node;
    }
};

// Trie class
class Trie {
private:
    Node* root; 

public:
    // Constructor 
    Trie() {
        root = new Node();
    }
    
    // To insert number in Trie
    void insert(int num) {
        // Start from the root
        Node* node = root;
        // Iterate each bit
        for (int i = 31; i >= 0; i--) {
            // Extract i-th bit
            int bit = (num >> i) & 1;
           /* If the current node doesn't 
           have a child node with the 
           current bit*/
            if (!node->containsKey(bit)) {
                node->put(bit, new Node());
            }
            node = node->get(bit);
        }
    }
    
    // Method to find the maximum XOR 
    int getMax(int num) {
        // Start from root
        Node* node = root;
        // Initialize maximum XOR value
        int maxNum = 0;
        // Iterate each bit
        for (int i = 31; i >= 0; i--) {
            // Extract the i-th bit 
            int bit = (num >> i) & 1;
            /*If the complement of the current bit 
            exists in the Trie update the maximum 
            XOR value with the current bit
            move to the child node corresponding to 
            the complement of the current bit
            Else move to the child node 
            corresponding to the current bit*/
            if (node->containsKey(1 - bit)) {
                
                maxNum |= (1 << i);
                
                node = node->get(1 - bit);
            } else {
                node = node->get(bit);
            }
        }
        // Return maximum XOR
        return maxNum;
    }
};

// Solution class
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        // Create Trie
        Trie trie;
        // Insert number
        for (int num : nums) {
            trie.insert(num);
        }
        
        // Maximum XOR value
        int maxi = 0;
        
        // Iterate each number
        for (int num : nums) {
            // Update the maximum XOR
            maxi = max(maxi, trie.getMax(num));
        }
        
        // Return maximum XOR value
        return maxi;
    }
};

// Main function
int main() {
    Solution solution;
    
    // Test case
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    
    // Print the input array
    cout << "Input: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    // Find and print the maximum XOR value
    int result = solution.findMaximumXOR(nums);
    cout << "Maximum XOR value: " << result << endl;
    
    return 0;
}
import java.util.*;

class Node {
    Node[] links = new Node[2];

    // To check if a specific bit key is present in the child nodes
    boolean containsKey(int bit) {
        return links[bit] != null;
    }

    // To get the child node corresponding to a specific bit
    Node get(int bit) {
        return links[bit];
    }

    // To set a child node at a specific index in the links array
    void put(int bit, Node node) {
        links[bit] = node;
    }
}

// Trie class
class Trie {
    private Node root;

    // Constructor
    Trie() {
        root = new Node();
    }

    // To insert number in Trie
    void insert(int num) {
        // Start from the root
        Node node = root;
        // Iterate each bit
        for (int i = 31; i >= 0; i--) {
            // Extract i-th bit
            int bit = (num >> i) & 1;
            /* If the current node doesn't 
           have a child node with the 
           current bit */
            if (!node.containsKey(bit)) {
                node.put(bit, new Node());
            }
            node = node.get(bit);
        }
    }

    // Method to find the maximum XOR 
    int getMax(int num) {
        // Start from root
        Node node = root;
        // Initialize maximum XOR value
        int maxNum = 0;
        // Iterate each bit
        for (int i = 31; i >= 0; i--) {
            // Extract the i-th bit 
            int bit = (num >> i) & 1;
            /*If the complement of the current bit 
            exists in the Trie update the maximum 
            XOR value with the current bit
            move to the child node corresponding to 
            the complement of the current bit
            Else move to the child node 
            corresponding to the current bit */
            if (node.containsKey(1 - bit)) {
                maxNum |= (1 << i);
                node = node.get(1 - bit);
            } else {
                node = node.get(bit);
            }
        }
        // Return maximum XOR
        return maxNum;
    }
}

// Solution class
class Solution {
    public int findMaximumXOR(int[] nums) {
        // Create Trie
        Trie trie = new Trie();
        // Insert number
        for (int num : nums) {
            trie.insert(num);
        }

        // Maximum XOR value
        int maxi = 0;

        // Iterate each number
        for (int num : nums) {
            // Update the maximum XOR
            maxi = Math.max(maxi, trie.getMax(num));
        }

        // Return maximum XOR value
        return maxi;
    }

    // Main function
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Test case
        int[] nums = {3, 10, 5, 25, 2, 8};

        // Print the input array
        System.out.print("Input: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();

        // Find and print the maximum XOR value
        int result = solution.findMaximumXOR(nums);
        System.out.println("Maximum XOR value: " + result);
    }
}
class Node:
    def __init__(self):
        self.links = [None] * 2

    # To check if a specific bit 
    # key is present in the child nodes
    def containsKey(self, bit):
        return self.links[bit] is not None

    # To get the child node 
    # corresponding to a specific bit
    def get(self, bit):
        return self.links[bit]

    # To set a child node at 
    # a specific index in the 
    # links array
    def put(self, bit, node):
        self.links[bit] = node


# Trie class
class Trie:
    def __init__(self):
        self.root = Node()

    # To insert number in Trie
    def insert(self, num):
        # Start from the root
        node = self.root
        # Iterate each bit
        for i in range(31, -1, -1):
            # Extract i-th bit
            bit = (num >> i) & 1
            # If the current node doesn't 
            # have a child node with the 
            # current bit
            if not node.containsKey(bit):
                node.put(bit, Node())
            node = node.get(bit)

    # Method to find the maximum XOR
    def getMax(self, num):
        # Start from root
        node = self.root
        # Initialize maximum XOR value
        maxNum = 0
        # Iterate each bit
        for i in range(31, -1, -1):
            # Extract the i-th bit
            bit = (num >> i) & 1
            '''If the complement of the current bit 
            exists in the Trie update the maximum 
            XOR value with the current bit
            move to the child node corresponding to 
            the complement of the current bit
            Else move to the child node 
            corresponding to the current bit'''
            if node.containsKey(1 - bit):
                maxNum |= (1 << i)
                node = node.get(1 - bit)
            else:
                node = node.get(bit)
        # Return maximum XOR
        return maxNum


# Solution class
class Solution:
    def findMaximumXOR(self, nums):
        # Create Trie
        trie = Trie()
        # Insert number
        for num in nums:
            trie.insert(num)

        # Maximum XOR value
        maxi = 0

        # Iterate each number
        for num in nums:
            # Update the maximum XOR
            maxi = max(maxi, trie.getMax(num))

        # Return maximum XOR value
        return maxi


# Main function
if __name__ == "__main__":
    solution = Solution()

    # Test case
    nums = [3, 10, 5, 25, 2, 8]

    # Print the input array
    print("Input:", " ".join(map(str, nums)))

    # Find and print the maximum XOR value
    result = solution.findMaximumXOR(nums)
    print("Maximum XOR value:", result)
class Node {
    constructor() {
        this.links = [null, null];
    }

    /*To check if a specific 
    bit key is present in 
    the child nodes*/
    containsKey(bit) {
        return this.links[bit] !== null;
    }

   /* To get the child 
   node corresponding 
   to a specific bit*/
    get(bit) {
        return this.links[bit];
    }

    /*To set a child node 
    at a specific index 
    in the links array*/
    put(bit, node) {
        this.links[bit] = node;
    }
}

// Trie class
class Trie {
    constructor() {
        this.root = new Node();
    }

    // To insert number in Trie
    insert(num) {
        // Start from the root
        let node = this.root;
        // Iterate each bit
        for (let i = 31; i >= 0; i--) {
            // Extract i-th bit
            const bit = (num >> i) & 1;
            /* If the current node doesn't 
           have a child node with the 
           current bit */
            if (!node.containsKey(bit)) {
                node.put(bit, new Node());
            }
            node = node.get(bit);
        }
    }

    // Method to find the maximum XOR 
    getMax(num) {
        // Start from root
        let node = this.root;
        // Initialize maximum XOR value
        let maxNum = 0;
        // Iterate each bit
        for (let i = 31; i >= 0; i--) {
            // Extract the i-th bit 
            const bit = (num >> i) & 1;
            /*If the complement of the current bit 
            exists in the Trie update the maximum 
            XOR value with the current bit
            move to the child node corresponding to 
            the complement of the current bit
            Else move to the child node 
            corresponding to the current bit */
            if (node.containsKey(1 - bit)) {
                maxNum |= (1 << i);
                node = node.get(1 - bit);
            } else {
                node = node.get(bit);
            }
        }
        // Return maximum XOR
        return maxNum;
    }
}

// Solution class
class Solution {
    findMaximumXOR(nums) {
        // Create Trie
        const trie = new Trie();
        // Insert number
        for (const num of nums) {
            trie.insert(num);
        }

        // Maximum XOR value
        let maxi = 0;

        // Iterate each number
        for (const num of nums) {
            // Update the maximum XOR
            maxi = Math.max(maxi, trie.getMax(num));
        }

        // Return maximum XOR value
        return maxi;
    }
}

// Main function
const solution = new Solution();

// Test case
const nums = [3, 10, 5, 25, 2, 8];

// Print the input array
console.log("Input:", nums.join(" "));

// Find and print the maximum XOR value
const result = solution.findMaximumXOR(nums);
console.log("Maximum XOR value:", result);

Complexity Analysis

Time Complexity: O(32N + 32M) where N is the length of the input array.

Insertion Phase (O(32N)): For each number in the input array, we need to insert its 32-bit binary representation into the Trie. Since there are N numbers, and each number has 32 bits, the time complexity for insertion is 32N.
Query Phase (O(32M)): For each number in the input array, we query the Trie to find the maximum XOR value. Again, for each of the M numbers, we need to traverse 32 bits. Hence, the time complexity for the querying phase is 32M.

Space Complexity: O(32N) where N is the length of the input array. This code has a linear space complexity with respect to the size of the input array and each number takes up space proportional to 32 which is the size in Binary Representation.

Problem List

Maximum XOR of two numbers in an array

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code