# 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]`