Leetcode 421. Maximum XOR of Two Numbers in an Array

Problem Explanation:

In this problem, we are given a non-empty array of numbers. We are asked to find the maximum possible result of XOR operation between any two numbers in the array. The XOR operation is a bitwise operation that returns 1 if the two compared bits are different, and 0 if they are the same.

For example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

The maximum result is 5 ^ 25 = 28.

Approach Explanation:

The solution approach involves the concept of Trie data structure and the properties of bitwise XOR operation. The core idea is to start from the most significant bit (MSB), if there exist two numbers a, b in the array such that a's MSB is 1 and b's MSB is 0, then the result of a ^ b will definitely larger than a ^ a and b ^ b. This is because the '1' at position i in a ^ b will contributes 2^i to the final result, where '1' at position (i - 1) only contributes 2^(i - 1).

We can solve this problem in O(n) time complexity using Trie data structure which is a tree-based data structure used for efficient retrieval of a key in a collection of strings. In this problem, we will use tri-nodes to store bits of each number in the form of binary search tree (0 at left child and 1 at right child)

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int findMaximumXOR(vector<int>& nums) {
6        const int maxNum = *max_element(begin(nums), end(nums));
7        if (maxNum == 0) return 0;
8        const int maxBit = static_cast<int>(log2(maxNum));  // Find maximum significant bit in maxNum
9        int ans = 0, mask = 0;
10
11        // Iterate from the most significant bit down to the least 
12        for (int i = maxBit; i >= 0; --i) {
13            // create mask from most significant to i-th bit
14            mask |= 1 << i;  
15
16            unordered_set <int> prefixes;   // Used to store prefix of all numbers with i+1 significant bits
17            for (const int num : nums)
18                prefixes.insert(num & mask);  // insert prefix in set
19
20            // Try to find two disjoint subset of prefix so We try to find answer by keep adding bit one by one from most significant to least
21            const int candidate = ans | (1 << i);  // possible max XOR of two numbers with i+1 bits.
22            for (const int prefix : prefixes)
23                if (prefixes.count(prefix ^ candidate)) {  // If there exist two prefix with XOR equal to candidate then we set that's bit in our answer
24                    ans = candidate;
25                    break;
26                }
27        }
28        return ans;
29    }
30};

Python Solution:

1
2python
3class Solution:
4    def findMaximumXOR(self, nums: List[int]) -> int:
5        ans = 0
6        mask = 0
7        for x in range(31, -1, -1):
8            mask = mask | (1 << x)
9            result_set = set()
10            for num in nums:
11                result_set.add(num & mask)
12            tmp = ans | (1 << x)
13            for prefix in result_set:
14                if tmp ^ prefix in result_set:
15                    ans = tmp
16                    break
17         
18        return ans

Java Solution:

1
2java
3import java.util.HashSet;
4
5public class Solution {
6    public int findMaximumXOR(int[] nums) {
7        int maxNum = nums[0];
8        for(int num: nums) maxNum = Math.max(maxNum, num);  // get max number to calculate max length
9        int L = (Integer.toBinaryString(maxNum)).length();  // calculate max length in binary representation
10
11        int maxXor = 0;
12        int currXor;
13        HashSet<Integer> prefixes = new HashSet<>();
14        for(int i = L - 1; i > -1; --i) {
15            maxXor <<= 1;  // shift 1 bit left
16            currXor = maxXor | 1;  // set the current bit
17            prefixes.clear();  
18
19            for(int num: nums) {
20                prefixes.add(num >> i);  // calculate the prefix and insert it into the set
21            }
22
23            for(int prefix : prefixes) {  // foreach prefix, find if there is another number which can make another number same as curr_xor prefix
24                if(prefixes.contains(currXor ^ prefix)) {
25                    maxXor = currXor;  // set max xor value to current xor value
26                    break;
27                }
28            }
29
30        }
31        return maxXor;
32    }
33}

JavaScript Solution:

1
2js
3var findMaximumXOR = function(nums) {
4    let mask = 0, max = 0;
5    for(let i = 31; i >= 0; i--){
6        mask = mask | (1 << i);
7        let set = new Set();
8        for(let num of nums){
9            set.add(num & mask); // save only left bits and ignore right bits
10        }
11        
12        let tmp = max | (1 << i); 
13        for(let prefix of set){
14            if(set.has(tmp ^ prefix)) { 
15                max = tmp;
16                break;
17            }
18        }
19    }
20    return max;
21};

C# Solution:

1
2csharp
3public class Solution {
4    public int FindMaximumXOR(int[] nums) {
5        int mask = 0, max = 0;
6        for(int i = 31; i >= 0; i--){
7            mask = mask | (1 << i);
8            var set = new HashSet<int>();
9            foreach(int num in nums){
10                set.Add(num & mask);
11            }
12
13            int tmp = max | (1 << i);
14            foreach(int prefix in set){
15              if(set.Contains(tmp ^ prefix)) {
16                  max = tmp;
17                  break;
18              }  
19            }
20        }
21
22        return max;
23    }
24}

Each solution has a time complexity of O(n), which meets the requested optimization. This is achieved through intelligent masking and bit manipulation, alongside effective use of the set data structure for fast presence checks.The code in each of these solutions can be broken down as follows:

1. A 'mask' variable is initiated. This variable is used to isolate the leading bits up to the current bit of the numbers in the array.

2. A 'max' variable is initiated to keep track of the maximum XOR value found.

3. A loop is started that iterates from the most significant bit down to the least significant bit.

4. The mask value is updated by adding (OR) the current bit (1 << i) to the existing mask.

5. A set is created and populated with the leading bits up to the current bit of the numbers in the array.

6. A 'tmp' variable is created by adding (OR) the current bit to the 'max' value. The purpose of 'tmp' is to test if the largest XOR value can be achieved with the current bit set to 1.

7. A loop is started over all the prefixes stored in the set. If the XOR of 'tmp' and the current prefix is found in the set, it means that there are at least two different numbers in the array that can achieve an XOR value of 'tmp', and 'max' is updated to 'tmp'.

8. When the loop finishes, the 'max' variable will hold the maximum XOR value that can be achieved with the numbers in the array.

In conclusion, this problem is a great example of using bitwise manipulation and a trie data structure to solve a problem efficiently. It challenges your understanding of the properties of the XOR operation and your ability to manipulate bits in a number to achieve desired outcomes. Despite the perceived complexity of the problem and the solution, it can be solved in linear time which makes it suitable for dealing with large datasets.