Patching Array Python Solution with Tests

lcpy gen -n 330   # by problem number
lcpy gen -s patching_array   # by problem name

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].

Input: nums = [1,2,2], n = 5
Output: 0

class Solution:
    # Time: O(len(nums) + log n)
    # Space: O(1)
    def min_patches(self, nums: list[int], n: int) -> int:
        patches = 0
        miss = 1  # smallest sum in [1, miss) that cannot be formed yet
        i = 0
        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                miss += nums[i]
                i += 1
            else:
                patches += 1
                miss += miss
        return patches