Python Solution


  • 0
    H

    The basic idea is very simple. We search from 0 in ascending order. And greedily add a new number if there's a hole----If you know what I mean.

    the variable _sum represent the current sum that we can cover. and you can see I only do ans += 1 when the new coming nums[index] is bigger than the _sum, and that's when the hole occur.

    Here's my code.

    Greedy

    class Solution(object):
        def minPatches(self, nums, n):
            """
            :type nums: List[int]
            :type n: int
            :rtype: int
            """
            _sum, ans, index = 0, 0, 0
            while _sum < n:
                while index < len(nums) and nums[index] <= _sum + 1:
                    _sum += nums[index]
                    index += 1
                if _sum < n:
                    ans += 1
                    _sum = _sum * 2 + 1
            return ans
            # 52ms ,beat 70.48%
    
    

Log in to reply
 

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