LeetCode-Solutions/Python/patching-array.py at master · fileset/LeetCode-Solutions · GitHub

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

Expand file tree