subject ： The original title is link （ difficult ）
label ： Greedy Algorithm
solution
Time complexity
Spatial complexity
Execution time
Ans 1 (Python)
O ( M + l o g N )
O ( 1 )
64ms (98.65%)
Ans 2 (Python)
Ans 3 (Python)
Solution 1 ：
class Solution:
def minPatches(self, nums: List[int], n: int) -> int:
# Handle the case that the array is empty
if not nums:
ans = 0
total = 0
while total < n:
total += (total + 1)
ans += 1
return ans
# When the array is not empty
else:
ans = 0
# To deal with the first 1 Before the number
total = 0
while total < nums[0] - 1:
total += (total + 1)
ans += 1
total += nums[0]
# Handle the number in the middle of the array
for i in range(1, len(nums)):
if nums[i] > n:
break
while total < nums[i] - 1:
total += (total + 1)
ans += 1
total += nums[i]
# Processing last 1 After the number
while total < n:
total += (total + 1)
ans += 1
return ans
