19. Maximum XOR of two numbers in an array

The problem can be found at the following link: Question Link

Problem Description

Given an array arr[] of non-negative integers, your task is to find the maximum XOR value that can be obtained by XORing any two distinct elements of the array.

Examples

Example 1:

Input:

arr[] = [25, 10, 2, 8, 5, 3]

Output:

28

Explanation:

The pair (25 ^ 5) gives the maximum XOR value which is 28.

Example 2:

Input:

arr[] = [1, 2, 3, 4, 5, 6, 7]

Output:

7

Explanation:

The pair (1 ^ 6) gives the maximum XOR value which is 7.

Constraints:

• $(2 \leq \text{arr.size()} \leq 5 \times 10^4)$

• $(1 \leq \text{arr[i]} \leq 10^6)$

My Approach

Greedy Bitmasking with HashSet

1. Iterate from MSB to LSB (31 to 0).

2. At each bit position:

   • Mask numbers to keep the current prefix.

   • Try setting the current bit in the result.

   • Use a set to check if there's a pair that can form this potential result.

3. This way, we greedily try to set each bit from left to right, ensuring it's possible.

Algorithm Steps:

1. Initialize max_xor = 0 and mask = 0.

2. Loop over 31 bits from high to low.

3. For each bit:

   • Add the bit to the mask.

   • Store all prefixes using the current mask.

   • Try setting the bit in max_xor, and see if two prefixes exist that form it.

4. If yes, update max_xor.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(32 × N), where N is the size of the array. We iterate through 32 bits and for each bit, we traverse the entire array once.

• Expected Auxiliary Space Complexity: O(N), used to store prefixes in a hash set at each bit position.

Code (C++)

class Solution {
public:
    int maxXor(vector<int>& a) {
        int max_xor = 0, mask = 0;
        unordered_set<int> s;
        for(int i = 30; i >= 0; i--) {
            mask |= (1 << i);
            s.clear();
            int temp = max_xor | (1 << i);
            for(int num : a) {
                int prefix = num & mask;
                if(s.count(temp ^ prefix)) { max_xor = temp; break; }
                s.insert(prefix);
            }
        }
        return max_xor;
    }
};

⚡ Alternative Approaches

📊 2️⃣ Trie-based Optimal

Algorithm Steps:

1. Build a Trie to store binary representations of numbers (MSB to LSB).

2. Insert all numbers into the Trie bit by bit.

3. Query each number against the Trie to find the maximum possible XOR by choosing opposite bits greedily.

class Solution {
    struct T { T* c[2]{}; } *r = new T;
    void i(int x) {
        T* n = r;
        for (int i = 31; i >= 0; --i) {
            int b = (x >> i) & 1;
            if (!n->c[b]) n->c[b] = new T;
            n = n->c[b];
        }
    }
    int q(int x) {
        T* n = r;
        int m = 0;
        for (int i = 31; i >= 0; --i) {
            int b = (x >> i) & 1;
            if (n->c[1 - b]) m |= 1 << i, n = n->c[1 - b];
            else n = n->c[b];
        }
        return m;
    }
public:
    int maxXor(vector<int>& a) {
        for (int x : a) i(x);
        int res = 0;
        for (int x : a) res = max(res, q(x));
        return res;
    }
};

📝 Complexity Analysis:

• Time Complexity: O(32n)

• Space Complexity: O(32n) (Trie storage)

✅ Why This Approach?

Optimal for large datasets. Uses bitwise Trie to efficiently compute maximum XOR in linear time.

📊 3️⃣ Brute-force (Check All Pairs)

Algorithm Steps:

1. Check all possible pairs of elements.

2. Compute XOR for each pair and track the maximum.

class Solution {
public:
    int maxXor(vector<int>& a) {
        int max_val = 0;
        for(int i = 0; i < a.size(); i++)
            for(int j = i + 1; j < a.size(); j++)
                max_val = max(max_val, a[i] ^ a[j]);
        return max_val;
    }
};

📝 Complexity Analysis:

• Time Complexity: O(n²)

• Space Complexity: O(1)

✅ Why This Approach?

Simple to implement for small arrays. Avoids complex data structures.

Note: This approach results in Time Limit Exceeded (TLE) for large inputs (fails ~30/1140 test cases due to time constraints).

🆚 Comparison of Approaches

Approach	⏱️ Time Complexity	🗂️ Space Complexity	✅ Pros	⚠️ Cons
Bitmask Greedy	🟢 O(31n)	🟡 O(n)	Balanced speed & memory	Complex bit manipulation
Trie-based	🟢 O(32n)	🟡 O(32n)	Optimal for large datasets	Higher memory usage
Brute-force	🔴 O(n²)	🟢 O(1)	Simple implementation	TLE for large inputs Impractical for large n

✅ Best Choice?

• Large Arrays: Use Bitmask Greedy or Trie-based.

• Small Arrays (n ≤ 1e3): Brute-force is acceptable.

Code (Java)

class Solution {
    public int maxXor(int[] arr) {
        int maxXor = 0, mask = 0;
        HashSet<Integer> set = new HashSet<>();
        for (int i = 30; i >= 0; i--) {
            mask |= (1 << i);
            set.clear();
            int temp = maxXor | (1 << i);
            boolean found = false;
            for (int num : arr) {
                int prefix = num & mask;
                if (set.contains(temp ^ prefix)) {
                    found = true;
                    break;
                }
                set.add(prefix);
            }
            if (found) maxXor = temp;
        }
        return maxXor;
    }
}

Code (Python)

class Solution:
    def maxXor(self, arr):
        max_xor, mask = 0, 0
        for i in range(30, -1, -1):
            mask |= (1 << i)
            prefixes = set()
            temp = max_xor | (1 << i)
            found = False
            for num in arr:
                prefix = num & mask
                if (temp ^ prefix) in prefixes:
                    found = True
                    break
                prefixes.add(prefix)
            if found:
                max_xor = temp
        return max_xor

Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count