LeetCode-Solution/Python/patching-array.py at master · paperfactory/LeetCode-Solution · GitHub

Repository navigation

21 lines (18 loc) · 492 Bytes

# Time: O(s + logn), s is the number of elements in the array

# Space: O(1)

class Solution(object):

def minPatches(self, nums, n):

"""

:type nums: List[int]

:type n: int

:rtype: int

"""

patch, miss, i = 0, 1, 0

while miss <= n:

if i < len(nums) and nums[i] <= miss:

miss += nums[i]

i += 1

else:

miss += miss

patch += 1

return patch