# LeetCode 330: Patching Array

## Problem Restatement

We are given a sorted positive integer array `nums` and an integer `n`.

We may add new numbers to `nums`. These added numbers are called patches.

After patching, every number in the range `[1, n]` must be formable as the sum of some elements from the array.

Return the minimum number of patches required. The array is sorted in ascending order, and `n` can be as large as `2^31 - 1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Sorted positive integer array `nums`, integer `n` |
| Output | Minimum number of patches needed |
| Goal | Every value from `1` to `n` can be formed as a subset sum |
| Important detail | Each array element can be used at most once in a sum |

Function shape:

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

## Examples

Example 1:

```text
Input: nums = [1, 3], n = 6
Output: 1
```

Before patching, possible sums include:

```text
1, 3, 4
```

The number `2` is missing.

Patch `2`.

Now with `[1, 2, 3]`, we can form:

```text
1, 2, 3, 4, 5, 6
```

So the answer is `1`.

Example 2:

```text
Input: nums = [1, 5, 10], n = 20
Output: 2
```

The two patches can be:

```text
[2, 4]
```

Example 3:

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

The original array already covers all numbers from `1` to `5`.

## First Thought: Track All Possible Sums

A direct idea is to store every subset sum we can form.

For every number in `nums`, update a set of reachable sums.

Then check which values from `1` to `n` are missing.

But this does not scale. Since `n` can be very large, storing every possible sum up to `n` can take too much time and memory.

We need a compressed way to describe what sums are reachable.

## Key Insight

Instead of storing every reachable sum, track the smallest positive integer that we cannot form yet.

Call it `miss`.

The invariant is:

```text
All numbers in [1, miss) can already be formed.
```

At the beginning:

```text
miss = 1
```

This means we cannot form `1` yet, and the covered range `[1, 1)` is empty.

Now consider the next available number `x`.

If:

```text
x <= miss
```

then we can use `x` to extend coverage.

Before using `x`, we can form every value in:

```text
[1, miss)
```

After adding `x`, we can also form:

```text
x + [0, miss)
```

That gives new sums from `x` to `x + miss - 1`.

Because `x <= miss`, this connects directly with the old covered range.

So coverage expands to:

```text
[1, miss + x)
```

Then update:

```text
miss += x
```

If the next number is greater than `miss`, then no existing number can form `miss`.

The best patch is exactly `miss`.

Patching `miss` expands coverage from:

```text
[1, miss)
```

to:

```text
[1, 2 * miss)
```

This is the largest possible expansion from one patch, because any patch larger than `miss` still leaves `miss` uncovered.

## Algorithm

Use three variables:

| Variable | Meaning |
|---|---|
| `miss` | Smallest positive integer that cannot be formed yet |
| `i` | Current index in `nums` |
| `patches` | Number of patches added |

Steps:

1. Set `miss = 1`.
2. Set `i = 0`.
3. Set `patches = 0`.
4. While `miss <= n`:
   1. If `i < len(nums)` and `nums[i] <= miss`, use `nums[i]`.
   2. Update `miss += nums[i]`.
   3. Move `i` forward.
   4. Otherwise, patch `miss`.
   5. Update `miss += miss`.
   6. Increment `patches`.
5. Return `patches`.

## Walkthrough

Use:

```text
nums = [1, 5, 10]
n = 20
```

Initial state:

```text
miss = 1
covered = [1, 1)
```

The next number is `1`.

Since `1 <= miss`, use it:

```text
miss = 1 + 1 = 2
covered = [1, 2)
```

Now we can form `1`.

The next number is `5`.

But `5 > miss`, so we cannot form `2`.

Patch `2`:

```text
miss = 2 + 2 = 4
patches = 1
covered = [1, 4)
```

Now we can form `1, 2, 3`.

The next number is still `5`.

But `5 > miss`, so we cannot form `4`.

Patch `4`:

```text
miss = 4 + 4 = 8
patches = 2
covered = [1, 8)
```

Now we can form `1` through `7`.

The next number is `5`.

Since `5 <= miss`, use it:

```text
miss = 8 + 5 = 13
covered = [1, 13)
```

The next number is `10`.

Since `10 <= miss`, use it:

```text
miss = 13 + 10 = 23
covered = [1, 23)
```

Now `miss = 23`, which is greater than `n = 20`.

So every number from `1` to `20` is covered.

The answer is:

```text
2
```

## Correctness

The algorithm maintains this invariant:

```text
Before each loop, every number in [1, miss) can be formed.
```

At the start, `miss = 1`, so the range `[1, 1)` is empty. The invariant is true.

If the next array number `nums[i]` is at most `miss`, then all old sums in `[1, miss)` remain formable. By adding `nums[i]` to any old formable sum, and also using `nums[i]` alone, we form every value from `nums[i]` through `nums[i] + miss - 1`.

Because `nums[i] <= miss`, this new interval touches or overlaps the old covered interval. So the full covered range becomes `[1, miss + nums[i])`.

If the next array number is greater than `miss`, then `miss` cannot be formed by existing numbers. All existing formable sums are less than `miss`, and the next unused array value is already too large. Therefore, some patch is necessary.

Among all possible patches, choosing `miss` is optimal. It immediately covers the missing value `miss`, and because all values in `[1, miss)` are already covered, it extends coverage to `[1, 2 * miss)`. Any smaller patch extends the range less, and any larger patch leaves `miss` uncovered.

So every patch made by the algorithm is necessary at that moment and gives the maximum possible coverage.

The loop stops only when `miss > n`. At that point, the invariant says every number in `[1, miss)` can be formed, which includes every number from `1` to `n`.

Therefore, the algorithm returns the minimum number of patches.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(len(nums) + log n)` | Each original number is consumed once, and each patch at least doubles `miss` |
| Space | `O(1)` | Only counters are used |

## Implementation

```python
class Solution:
    def minPatches(self, nums: list[int], n: int) -> int:
        miss = 1
        i = 0
        patches = 0

        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                miss += nums[i]
                i += 1
            else:
                miss += miss
                patches += 1

        return patches
```

## Code Explanation

Start with:

```python
miss = 1
```

This means `1` is the smallest value we cannot form yet.

The index `i` points to the next unused number in `nums`:

```python
i = 0
```

The answer counter starts at zero:

```python
patches = 0
```

The loop continues while some number up to `n` is still missing:

```python
while miss <= n:
```

If the next number can help extend the current covered range, use it:

```python
if i < len(nums) and nums[i] <= miss:
    miss += nums[i]
    i += 1
```

Otherwise, we must patch. The best patch is `miss` itself:

```python
else:
    miss += miss
    patches += 1
```

When the loop ends, `miss > n`, so the covered range includes all values from `1` to `n`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minPatches([1, 3], 6) == 1
    assert s.minPatches([1, 5, 10], 20) == 2
    assert s.minPatches([1, 2, 2], 5) == 0

    assert s.minPatches([], 7) == 3
    assert s.minPatches([2], 3) == 1
    assert s.minPatches([1, 2, 31, 33], 2147483647) == 28
    assert s.minPatches([1, 2, 3, 8], 20) == 2

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 3]`, `6` | Basic sample |
| `[1, 5, 10]`, `20` | Needs two patches |
| `[1, 2, 2]`, `5` | Already covered |
| `[]`, `7` | Only patches are available |
| `[2]`, `3` | Missing `1` at the start |
| Large `n` | Checks logarithmic patch growth |
| `[1, 2, 3, 8]`, `20` | Mixes original numbers and patches |