algoadvance

Leetcode 2932. Maximum Strong Pair XOR I

Problem Statement

Given an array of integers nums, find two integers a and b from the array such that the bitwise XOR of a and b is maximized. Return the maximum XOR value.

Clarifying Questions

  1. What is the range of the integers in the array?
    • Typically, array values are within the range of standard 32-bit integers, i.e., from -2^31 to 2^31-1 unless stated otherwise.
  2. Is the array guaranteed to have at least two elements?
    • Let’s assume the array always contains at least two elements since we need at least two numbers to calculate the XOR.
  3. Can the integers in the array be negative?
    • Yes, we should assume integers can be both positive and negative.
  4. Are there any constraints on the size of the array?
    • For the purpose of this question, let’s assume the array size (n) can be reasonably large, up to 10^5.

Strategy

  1. Naive Approach:
    • Compare all pairs and calculate their XOR values. Track the maximum XOR value found.
    • Time Complexity: (O(n^2)) which might be infeasible for large arrays.
  2. Optimized Approach using Trie:
    • Utilize a Trie data structure to store binary representations of numbers.
    • For each number, insert it into the Trie and then for each bit of the current number, try to find the opposite bit in the Trie to maximize the XOR.
    • This approach leverages bitwise properties and tries to minimize the maximum possible outcome with the right combination of bits.

Code

Here is the implementation using the Trie optimization:

#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>

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

class Trie {
private:
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(int num) {
        TrieNode* node = root;
        // Insert each bit to the Trie
        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 getMaxXOR(int num) {
        TrieNode* node = root;
        int max_xor = 0;
        for (int i = 31; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (node->children[1 - bit]) {
                max_xor |= (1 << i);
                node = node->children[1 - bit];
            } else {
                node = node->children[bit];
            }
        }
        return max_xor;
    }
};

int findMaximumXOR(std::vector<int>& nums) {
    Trie trie;
    int max_xor = 0;
    for (int num : nums) {
        trie.insert(num);
        max_xor = std::max(max_xor, trie.getMaxXOR(num));
    }
    return max_xor;
}

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

Time Complexity

Each number is inserted into the Trie and checked for maximum XOR, resulting in a relatively optimal and feasible solution.

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