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).
Top comments (0)