[Leetcode]421. Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ ij < n.
Could you do this in O(n) runtime?

This problem could be solved by either trie (644ms in Python) or bit operations + hashnap (116ms in Python). Both of them will be introduced here with implementations. If you are not familiar with trie, feel free to check: Intro to Trie (Prefix Tree) – FEAT. Leetcode 208. Implement Trie.

The general idea is to greedily pursue 1 for each position in the binary representation of the output starting from the most significant bit to the least significant bit. To search the input array systematically and to avoid duplicated computations, two approaches are suggested.

Using trie

We can preprocess the input array and store the binary representations of all elements into a trie. Noticing that 0 \leq a_i<2^{31}, we would store each element as a 32-bit number, therefore the height of the trie is also 32.

Build a trie with binary representations.

After that, we need to search through the trie for each element in the input, trying to pursue 1 for each bit from the most significant bit to the least significant bit.

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        trie = {}
        # build the trie
        for num in nums:
            p = trie
            for j in range(31,-1,-1):
                bit = num >> j & 1 # shift is computed before &
                if bit not in p:
                    p[bit] = {}
                p = p[bit]
        ret = -1
        for num in nums:
            p = trie
            cnt = 0
            for j in range(31,-1,-1):
                # get the bit from left to right
                bit = num >> j & 1
                if bit ^ 1 in p:
                    p = p[bit^1]
                    cnt += (1 << j)
                else:
                    p = p[bit]
            ret = max(ret,cnt)
        return ret

Using bit operations and hashmap – two sum

This approach is the most voted post in the submission by @StefanPochmann. It adopts the strategy which tries to find the answer bit by bit, also from the most significant bit to the least significant bit.

To find the value for the k-th bit (counting from left), it would firstly store the k-bit prefix of each element into one hashmap prefix. Noticing that:

if a^b=c, then a^c=b and a=b^c,

we can first put 1 on the k-th bit to the answer as ans^1, and search prefix to check if we can find two elements p and q in prefix such that p^q==ans^1. If so, we can safely set the bit as 1, else 0. To find p^q==ans^1, we can check given p in prefix, whether ans^1^p is also in prefix. From this point of view, this is more like a two sum question.

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = 0
        for i in range(31,-1,-1):
            ans <<= 1
            prefix = {num >> i for num in nums}
            ans += any(ans^1^p in prefix for p in prefix)
        return ans

Reference

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments