Patching Array

Determine the minimum number of patches to cover all sums from 1 to n.

greedy arrays prefix-sums

Given a sorted integer array `nums` (strictly increasing, all positive) and an integer `n`, you can add any positive integer to the array. After adding the minimum number of integers, every integer in the range `[1, n]` must be representable as a sum of some subset of the array. You may use each element at most once.

Implement the function:

```python
def minPatches(nums: list[int], n: int) -> int:
```

Return the minimum number of patches (added integers) required.

Constraints

<= len(nums) <= 1000
<= nums[i] <= 10^4
<= n <= 2^31 - 1
nums is strictly increasing and contains positive integers.

Example

>>> minPatches([1, 3], 6)
1
>>> minPatches([1, 5, 10], 20)
2
>>> minPatches([1, 2, 2], 5)
0
>>> minPatches([], 7)
3

40 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about the largest prefix sum you can cover with the existing numbers.

If the next needed number is missing, patching that number doubles your coverage.

Iterate through nums and patch only when the current coverage is insufficient.

The greedy choice of patching the smallest missing number is always optimal.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.