Maximum XOR of two numbers in an array

Dec 18, 2024 • 2 mins read

Dhaval Trivedi

Co-founder, Airtribe

Problem Overview

In this LeetCode problem, you are tasked with finding the maximum XOR of two numbers in a given array. The challenge lies in efficiently determining the maximum XOR value, exploiting data structures that optimize the searching and comparing process.

The original problem URL can be found here.

Understanding the Problem

Problem Statement

You are given an integer array nums and need to compute the maximum result of nums[i] XOR nums[j] where 0 <= i, j < n. The key is to maximize this XOR for any two numbers in the input array.

Example

Suppose nums = [3, 10, 5, 25, 2, 8].

The maximum XOR value can be achieved by XORing 5 and 25 (5 XOR 25 = 28). Thus, the answer is 28.

Intuition

Bitwise XOR of two numbers results in a number whose binary representation has bits set to 1 where the corresponding bits of the operands are different. The task is to find two numbers in the array that have the largest difference in their binary representation.

Key DSA Concepts and Theory

Trie Data Structure

A Trie (pronounced "try") is a tree-like data structure that is used to efficiently store and search strings. In this problem, we extend this concept to numbers, treating each bit of a number as a character in a string.

Properties of Trie:

It is efficient for prefix searching, which fits our need as we want to compare bits of numbers.
Instead of storing the numbers directly, we store their binary representation.

A binary Trie will have each node potentially branching into two children, representing a 0-bit or a 1-bit.

XOR Operation

XOR is a binary operation where the resulting digit is 1 if the bits are different and 0 if they are the same. This operation is both associative and commutative, hence (a XOR b XOR b = a), which will be utilized in searching for the maximum XOR pair.

Solution Approach

Step-by-Step Explanation

Insert Numbers into a Trie:
- Convert each number into its 32-bit binary representation.
- Insert these bit representations into a binary Trie. Each bit of the number will determine the path in the trie (0 to left, 1 to right).
Maximize XOR:
- For each number, attempt to find another number in the Trie that maximizes the XOR result.
- Traverse the Trie to select the opposite bit at each level, if possible, to maximize the XOR value.

The key insight here is that to maximize XOR, any 0 bit wishes to match with 1 bit and vice versa, maximizing differences in corresponding bit positions.

Code Implementation

C++

class TrieNode {
public:
    TrieNode* children[2];
    TrieNode() {
        children[0] = nullptr;
        children[1] = nullptr;
    }
};

class Solution {
private:
    TrieNode* root = new TrieNode();

    void insert(int num) {
        TrieNode* node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!node->children[bit]) {
                node->children[bit] = new TrieNode();
            }
            node = node->children[bit];
        }
    }

    int findMaximumXOR(int num) {
        TrieNode* node = root;
        int maxXOR = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node->children[1 - bit]) {
                maxXOR = (maxXOR << 1) | 1;
                node = node->children[1 - bit];
            } else {
                maxXOR = maxXOR << 1;
                node = node->children[bit];
            }
        }
        return maxXOR;
    }

public:
    int findMaximumXOR(vector<int>& nums) {
        for (int num : nums) {
            insert(num);
        }
        int max_xor = 0;
        for (int num : nums) {
            max_xor = max(max_xor, findMaximumXOR(num));
        }
        return max_xor;
    }
};

Java

class TrieNode {
    TrieNode[] children = new TrieNode[2];
}

class Solution {
    private TrieNode root = new TrieNode();

    private void insert(int num) {
        TrieNode node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.children[bit] == null) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
        }
    }

    private int findMaximumXOR(int num) {
        TrieNode node = root;
        int maxXOR = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.children[1 - bit] != null) {
                maxXOR = (maxXOR << 1) | 1;
                node = node.children[1 - bit];
            } else {
                maxXOR <<= 1;
                node = node.children[bit];
            }
        }
        return maxXOR;
    }

    public int findMaximumXOR(int[] nums) {
        for (int num : nums) {
            insert(num);
        }
        int maxXOR = 0;
        for (int num : nums) {
            maxXOR = Math.max(maxXOR, findMaximumXOR(num));
        }
        return maxXOR;
    }
}

Time and Space Complexity Analysis

Time Complexity:
- Inserting a number into the Trie takes O(32) because each number is represented by at most 32 bits. The time complexity for building the Trie for all numbers is O(n * 32), which simplifies to O(n).
- Finding the maximum XOR for each number also takes O(32), leading to an overall query time of O(n).
Space Complexity:
- The space taken by the Trie is at most O(n * 32), which simplifies to O(n), as each bit node can potentially branch two ways across the numbers inserted.

Common Mistakes to Avoid

Incorrect Bit Manipulation: Ensure that the bit extraction and manipulation (shifts and masks) is correctly implemented to avoid wrong paths in the Trie.
Trie Initialization: All nodes in the Trie should be correctly initialized to avoid null pointer exceptions.

Additional Resources and References

Through this structured approach leveraging the Trie data structure, this problem showcases an efficient route to solve maximum XOR-related challenges using bit manipulations.

Terms & Conditions Privacy Policy Refund Policy