Leetcode September Day16

Problem

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 ≤ i, j < n.

Could you do this in O(n) runtime?

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

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.
"""

Approach -
The brute force approach would be to consider all pairs and return the pair with maximum xor.

ans = float('-inf')
for i in range(len(arr)):
    for j in range(i, len(arr)):
        ans = max(ans, arr[i]^arr[j])
return ans

Time Complexity of this approach is O(n^2) and space complexity is O(1).

How can we optimize it ?

We know that a^b = 1 if a != b . (assuming a, b to be either 0 or 1).
So, xor of two numbers will be maximum if the they differ in their bits at most places.
For example 11001 will give max xor with 00110 which is 11111.
So, We will first convert all numbers into their binary string representation. Then for each number we will try to find the number with opposite bits (as close as possible) and we update the answer.

Now, to find the number with opposite bits we will be using tries. The time for search in trie is O(len(word)).

Solution

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        bin_list = ["{0:b}".format(el) for el in nums]
        max_len = len(max(bin_list, key = lambda x: len(x)))
        bin_list = ["0"*(max_len - len(el)) + el for el in bin_list]
        ans = float('-inf')
        # create a trie and for each representation try to find the exact opposite as much as possible
        trie = {}
        for word in bin_list:
            parent = trie
            for char in (word):
                if char in parent:
                    parent = parent[char]
                else:
                    parent[char] = {}
                    parent = parent[char]
        # now for each item in binary_list, try to find the opposite
        ans = float('-inf')
        for word in bin_list:
            parent = trie
            curr = ''
            for idx, char in enumerate(word):
                to_find = '1' if char == '0' else '0'
                if to_find in parent:
                    curr += to_find
                    parent = parent[to_find]
                else:
                    curr += char
                    parent = parent[char]
                if idx == len(word) - 1:
                    ans = max(ans, int(word, 2) ^ int(curr, 2) )
        return ans

Time Complexity -
For creating binary list = O(n*log(len_of_digits)) = O(n)
for each word we are search in trie = O(n*log(len_of_digits)) = O(n).
So, approximately the time complexity of this solution is O(n).

Blog

Leetcode September Day16

Shailesh Kumar

Join Our Newsletter. No Spam, Only the good stuff.

Related