421

421. Maximum XOR of Two Numbers in an Array (Medium)

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 * 105
• 0 <= nums[i] <= 231 - 1

Companies: Amazon, Adobe, Google, Bloomberg, Apple

Related Topics:
Array, Hash Table, Bit Manipulation, Trie

Similar Questions:

• Maximum XOR With an Element From Array (Hard)
• Maximum XOR After Operations (Medium)
• Sum of Prefix Scores of Strings (Hard)
• Minimize XOR (Medium)
• Maximum Strong Pair XOR I (Easy)
• Maximum Strong Pair XOR II (Hard)

Solution 1. Trie

Flatten the bits information of the array into a Trie. For each number in array, use Trie to find the maximum value it can get using xor.

// OJ: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie
struct TrieNode {
    TrieNode *next[2] = {};
};
class Solution {
    void add(TrieNode *node, int n) {
        for (int i = 31; i >= 0; --i) {
            int b = n >> i & 1;
            if (!node->next[b]) node->next[b] = new TrieNode();
            node = node->next[b];
        }
    }
    int maxXor(TrieNode *node, int n) {
        int ans = 0;
        for (int i = 31; i >= 0; --i) {
            int b = n >> i & 1;
            if (node->next[1 - b]) { // if we can go the opposite direction, do it.
                node = node->next[1 - b];
                ans |= 1 << i;
            } else {
                node = node->next[b];
            }
        }
        return ans;
    }
public:
    int findMaximumXOR(vector<int>& A) {
        TrieNode root;
        int ans = 0;
        for (int n : A) {
            add(&root, n);
            ans = max(ans, maxXor(&root, n));
        }
        return ans;
    }
};

Solution 2.

Assume we have a goal number that we can form using the XOR value of two numbers in A, we can use an unordered_set<int> s to store all the numbers, and for a given number A[i], we check if its counterpart A[i] ^ goal is in s.

// OJ: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
class Solution {
public:
    int findMaximumXOR(vector<int>& A) {
        if (A.size() == 1) return 0;
        unordered_set<int> s;
        int mask = 0, ans = 0, msb = log2(*max_element(begin(A), end(A)));
        for (int i = msb; i >= 0; --i) {
            mask |= 1 << i;
            s.clear();
            for (int n : A) s.insert(n & mask);
            int next = ans | (1 << i);
            for (int prefix : s) {
                if (!s.count(next ^ prefix)) continue;
                ans |= 1 << i;
                break;
            }
        }
        return ans;
    }
};

Or faster.

// OJ: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int findMaximumXOR(vector<int>& A) {
        if (A.size() == 1) return 0;
        int ans = 0, mask = 0;
        unordered_set<int> s;
        int msb = log2(*max_element(begin(A), end(A)));
        for (int i = msb; i >= 0; --i){
            mask |= (1 << i);
            int goal = ans | (1 << i); // try to find two numbers `a` and `b` that can form `goal` via `(mask & a) ^ (mask ^ b)`.
            for (int n : A) {
                n &= mask;
                if (s.count(goal ^ n)){
                    ans = goal; // If found, update answer with `goal`, and break
                    break;
                }
                s.emplace(n); // If not found, put `mask & a` into set
            }
            s.clear();
        }
        return ans;
    }
};

TODO

There are faster solutions in "Accepted Solutions Runtime Distribution". Learn those solutions.