Problems

# Patching Array

## Problem

Given a sorted positive integer array `nums` and an integer `n`, add/patch elements to the array such that any number in range `[1, n]` inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

### Example #1

`nums = [1, 3]`, `n = 6`

Return 1.

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.

### Example #2

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

Return 2.

The two patches can be [2, 4].

### Example #3

nums = [1, 2, 2], n = 5

Return 0.

## Solution

Greedy.

Assume there is not any element in array.

`[] -> []`, the next missing value is `1`.

`[1] -> [1]`, the next missing value is `2`.

`[1, 2] -> [1, 2, 3]`, the next missing value is `4`.

`[1, 2, 4]` -> `[1, 2, 3, 4, 5, 6, 7]`, the next missing value is `8`.

The greedy idea here is to get as many values as possible. Meanwhile, if we already can get values `[1, k]` and add a new value `p`, we are supposed to get `[1, k]` and `[p, p+k]`. If `p <= k+1`, it would be `[1, p+k]`.

For example, `[1, 1, 5, 10]` and `n = 20`.

`[] -> []`, the next missing value is `1`, and `1` is in given array.

`[1] -> [1]`, there is another `1 <= max value`, so we can get `[1, 1]`, `1`, and `[2, 2]`.

`[1, 1] -> [1, 2]`, the next missing value is `3`. Add `3`.

`[1, 1, 3] -> [1, 2, 3, 4, 5]`, In array, `5 <= max value` in range, so we can get `[1, 5]`, `5` and `[6, 10]`.

`[1, 1, 3, 5] -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`, Then we get `[1, 10]`, `10` and `[11, 20]`.

`[1, 2, 3, 5, 10] -> [1, 2,..., 20]`