Patching Array

Problem: Patching Array

We can simply check intervals in given numbers and make sure numbers in intervals can all be summed up to. To make sure number N is checked, we can add N+1 to end of array.

While checking numbers from 1, if we miss some number, we simply patch the number to our array. If number X is not missed, it's clear that numbers from X+1 to X+X are not missed since numbers from 1 to X are not missed, which can make our code run faster.

Code in Python:

class Solution(object):
    def minPatches(self, nums, n):
        """
        :type nums: List[int]
        :type n: int
        :rtype: int
        """
        ans, maxSum = 0, 0
        nums.append(n+1)
        for i in nums:
            num = min(i,n+1)
            while maxSum + 1 < num:
                maxSum += maxSum + 1
                ans += 1
            maxSum += num
        return ans