Problem Statement

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.

Examples

Example 1:

Input: nums = [3, 9, 10, 5, 1]
Output: 15

Explanation: The maximum XOR value is 10 XOR 5 => 15.

Example 2:

Input: nums = [26, 49, 30, 15, 69]
Output: 116

Explanation: The maximum XOR value is 69 XOR 49 => 116.

Example 3:

Input: nums = [3, 10, 5, 25, 2, 8]
Output: 28 (5 XOR 25)

Explanation: All possible XOR results:
3⊕10=9  
3⊕5=6  
3⊕25=26  
3⊕2=1  
3⊕8=11  
10⊕5=15  
10⊕25=19  
10⊕2=8  
10⊕8=2  
5⊕25=28  
5⊕2=7  
5⊕8=13  
25⊕2=27  
25⊕8=17  
2⊕8=10  

Different Approaches

1️⃣ Brute Force Approach

Approach:

• Iterate over every pair in the array.
• Compute the XOR for each pair.
• Keep track of the maximum XOR found.

Code:

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int maxXor = 0;
        int n = nums.size();

        // Iterate through all pairs
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                maxXor = max(maxXor, nums[i] ^ nums[j]);
            }
        }
        return maxXor;
    }
};

int main() {
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    Solution sol;
    cout << "Maximum XOR: " << sol.findMaximumXOR(nums) << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N ^ 2)
  • It checks for the every pair.
• Space Complexity:O(1)

2️⃣ Using Trie

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:

1. 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.
2. 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.
3. Initialize Maximum XOR Value: Start from the root node and set the maximum XOR value to 0.
4. 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.
5. Return the Result: After processing all bits of all numbers, return the maximum XOR value obtained.

Dry Run:

Code:

#include <iostream>
#include <vector>
using namespace std;

// TrieNode class representing a single node in the Trie
class TrieNode {
public:
    TrieNode* children[2]; // Only two children for bits (0 and 1)
    
    TrieNode() {
        children[0] = children[1] = nullptr;
    }
};

// Trie class for inserting numbers and finding max XOR pairs
class Trie {
public:
    TrieNode* root;

    Trie() {
        root = new TrieNode(); // Initialize root node
    }

    // Function to insert a number into the Trie
    void insert(int num) {
        TrieNode* current = root;

        // Insert bits from the 31st (MSB) to 0th (LSB)
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1; // Extract the i-th bit
            if (!current->children[bit]) {
                current->children[bit] = new TrieNode();
            }
            current = current->children[bit];
        }
    }

    // Function to find the maximum XOR for a given number
    int getMaxXOR(int num) {
        TrieNode* current = root;
        int maxXOR = 0;

        // Traverse from the 31st bit (MSB) to the 0th bit (LSB)
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1; // Extract the i-th bit
            int oppositeBit = 1 - bit; // Look for the opposite bit (to maximize XOR)

            if (current->children[oppositeBit]) { // If opposite bit exists, take it
                maxXOR |= (1 << i); // Set the i-th bit in maxXOR
                current = current->children[oppositeBit];
            } else { // Otherwise, take the same bit
                current = current->children[bit];
            }
        }
        return maxXOR;
    }
};

// Solution class to solve the problem
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        Trie trie; // Create a Trie object

        // Insert all numbers into the Trie
        for (int num : nums) {
            trie.insert(num);
        }

        int maxXOR = 0;

        // Check the maximum XOR value for each number
        for (int num : nums) {
            maxXOR = max(maxXOR, trie.getMaxXOR(num));
        }

        return maxXOR;
    }
};

int main() {
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    Solution sol;
    cout << "Maximum XOR: " << sol.findMaximumXOR(nums) << endl;
    return 0;
}

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.