Python O(n) solution


  • 0
    J
    def minPatches(self, nums, n):
        # Number of patches
        count = 0
        # Empty List case to grow to n
        if len(nums) == 0:
            loopNum = 1
            count = 1
            while loopNum * 2 <= n:
                loopNum *= 2
                count += 1
            return count
        
    
        # Add 1 to the list if not exists
        if nums[0] != 1:
            count = 1
            nums.append(1)
            nums.sort()
    
        # Index  
        current = 1
        # next value proposed to be
        N = 1
        # sum of all values before N
        addup = 0
        # sum(N-1) + N < n
        while addup + N < n:
            addup += N # update sum
            
            # if current element is less than N, assign N the array element value
            if current <= len(nums) - 1 and nums[current] <= addup + 1:
                N = nums[current]
            else:
                N = addup + 1
                if N not in nums:
                    print(N)
                    nums.append(N)
                    nums.sort()
                count += 1
            current += 1
        return count

  • 0
    D

    why do think that this is O(n)?
    is the sorting already O(nlogn) with timsort?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.