Formatted question description: https://leetcode.ca/all/421.html

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.

Follow up: Could you do this in O(n) runtime?

 

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 = [0]
Output: 0

Example 3:

Input: nums = [2,4]
Output: 6

Example 4:

Input: nums = [8,10,2]
Output: 10

Example 5:

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

 

Constraints:

• 1 <= nums.length <= 2 * 104
• 0 <= nums[i] <= 231 - 1

Related Topics:
Bit Manipulation, Trie

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/

// Time: O(N)
// Space: O(1)
// Ref: https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie
struct TrieNode {
    TrieNode *next[2] = {};
};
class Solution {
    void addNode(TrieNode *node, int n) {
        for (int i = 31; i >= 0; --i) {
            int bit = (n >> i) & 1;
            if (!node->next[bit]) node->next[bit] = new TrieNode();
            node = node->next[bit];
        }
    }
public:
    int findMaximumXOR(vector<int>& A) {
        TrieNode root;
        for (int n : A) addNode(&root, n);
        int ans = 0;
        for (int n : A) {
            auto node = &root;
            int val = 0;
            for (int i = 31; i >= 0; --i) {
                int bit = (n >> i) & 1;
                if (node->next[1 ^ bit]) {
                    val |= 1 << i;
                    node = node->next[1 ^ bit];
                } else node = node->next[bit];
            }
            ans = max(ans, val);
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

// 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) {
        unordered_set<int> s;
        int mask = 0, ans = 0;
        for (int i = 31; 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;
    }
};

Java

class Solution {
    public int findMaximumXOR(int[] nums) {
        int xor = 0;
        int mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i);
            Set<Integer> prefixSet = new HashSet<Integer>();
            for (int num : nums)
                prefixSet.add(mask & num);
            int temp = xor | (1 << i);
            for (int prefix : prefixSet) {
                if (prefixSet.contains(prefix ^ temp)) {
                    xor = temp;
                    break;
                }
            }
        }
        return xor;
    }
}

All Problems

All Solutions