Skip to content

Maximum XOR of Two Numbers in an Array⚓︎

Link

Description⚓︎

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

Example 1:

  • Input: nums = [3,10,5,25,2,8]
  • Output: 28
  • Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

  • Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
  • Output: 127

Constraints:

  • 1 <= nums.length <= 2 * 10^5
  • 0 <= nums[i] <= 2^31 - 1

Solution⚓︎

Way 1 (Trie)⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
private:
    static const int N = 3e6 + 1;
    int son[N][2] {0};
    int cnt = 0;
    int high;

public:
    int findMaximumXOR(vector<int>& nums) {
        build(nums);
        int res = 0;
        for (int num : nums) {
            res = max(res, maxXOR(num));
        }
        return res;
    }

    void build(const vector<int>& nums) {
        int maxNum = *max_element(nums.begin(), nums.end());
        maxNum = max(maxNum, 1);  // to pass the test case: [0]
        high = 31 - __builtin_clz(maxNum);  // Finds the highest bit position in the maximum number
        for (int num : nums) {
            insert(num);
        }
    }

    void insert(int num) {
        int current = 0;
        for (int i = high; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!son[current][bit]) {
                son[current][bit] = ++cnt;
            }
            current = son[current][bit];
        }
    }

    int maxXOR(int num) {
        int res = 0, current = 0;
        for (int i = high; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int want = bit ^ 1;  // We want the opposite bit if possible for maximum XOR
            // If the opposite bit is not available
            if (!son[current][want]) {
                want ^= 1;  // Switch back to the original bit
            }
            res |= (bit ^ want) << i;
            current = son[current][want];
        }
        return res;
    }
};

Way 2 (Hash Set)⚓︎

See reference (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int maxNum = *max_element(nums.begin(), nums.end());
        int high = maxNum ? 31 - __builtin_clz(maxNum) : -1;

        int res = 0, mask = 0;
        unordered_set<int> seen;

        for (int i = high; i >= 0; i--) {
            seen.clear();
            int better = res | (1 << i);

            for (int x : nums) {
                x = (x >> i) << i;
                if (seen.contains(better ^ x)) {
                    res = better;
                    break;
                }
                seen.insert(x);
            }
        }

        return res;
    }
};
  • Time complexity: \(O\left( n\cdot \log \left( \max \left( nums \right) \right) \right)\);
  • Space complexity: \(O(n)\).