1
class Solution:
2
    def minPatches(self, nums: List[int], n: int) -> int:
3
        # pre-process for convenience
4
        nums.append(n + 1)
5
        t = 1
6
        sum = 1
7
        rs = 0
8
        if nums[0] != 1:
9
            nums = [1] + nums
10
            rs += 1
11
        # the idea is sum from index 0 to index i should cover 1 to that sum*2 then we go form left to right to cover upto n
12
        while sum < n:
13
            if sum < nums[t] - 1:
14
                sum += sum + 1
15
                rs += 1
16
            else:
17
                sum += nums[t]
18
                t += 1
19
        return rs