Question

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.

Constraints:
1 <= nums.length <= 2 * 105
0 <= nums[i] <= 231 - 1

Approach: I have solved using Triewhere I add each elements and after adding I search for the number which can result in maximum xor.

Solution:

class TreeNode:
    def __init__(self, value = '-1'):
        self.val = value
        self.left = None
        self.right = None
class Solution(object):
    def findMaximumXOR(self, a):
        root = TreeNode()
        msf = float('-inf')
        for i in a:
            bits = format(i, 'b').zfill(31)
            node = root
            for bit in bits:
                if bit == '0' and node.left:
                    node = node.left
                elif bit == '0':
                    new_node = TreeNode('0')
                    node.left = new_node
                    node = new_node
                
                if bit == '1' and node.right:
                    node = node.right
                elif bit == '1':
                    new_node = TreeNode('1')
                    node.right = new_node
                    node = new_node
            
            ssf=''
            node = root
            for bit in bits:
                if bit == '0' and node.right:
                    ssf  = '1'
                    node = node.right
                elif bit == '1' and node.left:
                    ssf  = '1'
                    node = node.left
                elif node.left:
                    ssf  = '0'
                    node = node.left
                else:
                    ssf  = '0'
                    node = node.right

            val = int(ssf, 2)
            msf = max(msf, val)
        return msf

Question: What is the time complexity of the above solution? In my opinion it is O(N) where N is the number of element in nums.

CodePudding user response：

your time complexity is O(N*Log2(max(nums))).

CodePudding user response：

It is actually O(n*(log2(max_num)**2)), because for each bit you do string concatenation, which is not O(1) in Python:

        for bit in bits: # this entire for loop is O(bits**2)
            if bit == '0' and node.right:
                ssf  = '1' # this is not O(1), it is O(len(bits))
        ...

Avoid strings, use bitwise operators to get true O(n*log(max_num)).