# LeetCode Patching Array

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]`, which form possible sums of: `1, 3, 4`.
Now if we add/patch `2` to nums, the combinations are: `, , , [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`.

## Java Solution

The following algorithm is from https://discuss.leetcode.com/topic/35494/solution-explanation

We define `miss` to be the smallest number that will miss, which means, given an input {1…m}, we can build all sums in [0, miss).  For the next number `x` in the array, if `x <= miss`, then we can build sums in the range `[0, miss + x)`, thus there is no need to add a number.

If the array is empty, or the next number `x` in the array is larger than `miss`, we have to add a number to get `miss`. The best strategy is to add `miss` itself. Then our next range is `[0, miss + miss)`

I also used an example below to describe how this method works.