algoadvance

Leetcode 421. Maximum XOR of Two Numbers in an Array

Problem Statement

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

Clarifying Questions

  1. Constraints on nums:
    • How large can the array nums be?
    • What values can the elements in nums take?

    These questions will help us understand the potential computational complexity and any edge cases we need to handle.

  2. Output requirements:
    • Is there a preference for the pair of indices (i, j) that produce the maximum XOR?

Strategy

  1. Understanding XOR:
    • The XOR operation (exclusive OR) outputs 1 only where bits differ, i.e., 1 XOR 0 = 1 and 0 XOR 1 = 1, otherwise it outputs 0.
    • To maximize the XOR of two numbers, we need to have the most significant bits differ as much as possible.
  2. Optimal Solution:
    • Trie-based Approach: We can use a trie (prefix tree) to efficiently store the binary representation of numbers and maximize the XOR.
    • Steps:
      1. Insert each number from nums into the trie.
      2. For each number in nums, try to find the maximum XOR it can get with numbers already in the trie by traversing the trie in a way that tries to maximize the differing bits.
  3. Complexity:
    • Time Complexity: Constructing the trie will take O(n * L) time, where n is the number of elements and L is the number of bits (typically 32 for integers). Finding the maximum XOR can also be done in O(n * L).
    • Space Complexity: The trie will take O(n * L) space.

Code

Here’s the implementation in C++ using a Trie (prefix tree):

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

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

class Solution {
public:
    TrieNode* root;
    
    Solution() {
        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(const vector<int>& nums) {
        // Insert all numbers into the Trie
        for (int num : nums) {
            insert(num);
        }
        
        int maxXOR = 0;
        
        // Find the maximum XOR for each number with the Trie
        for (int num : nums) {
            TrieNode* node = root;
            int currentXOR = 0;
            
            for (int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                // To maximize XOR, we look for the opposite bit (1 - bit)
                if (node->children[1 - bit]) {
                    currentXOR = (currentXOR << 1) | 1;
                    node = node->children[1 - bit];
                } else {
                    currentXOR = (currentXOR << 1);
                    node = node->children[bit];
                }
            }
            
            maxXOR = max(maxXOR, currentXOR);
        }
        
        return maxXOR;
    }
};

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

Time Complexity

This should solve the problem efficiently for typical input sizes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI