# 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], [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.

### 分析​

• nums中必然包含1，如果不包含1，那么[1,n]这个范围中的1就没法实现
• 其次数组中的元素不能重复使用，如果允许重复使用，那么把1重复多次，就可以组成任意整数。

miss[0,n]中缺少的最小整数，意味着我们可以实现[0,miss)范围内的任意整数。

1. 如果数组中有某个整数x<=miss, 那么我们可以把[0,miss)区间的所有整数加上x，区间变成了[x, miss+x)，由于区间[0,miss)[x, miss+x)重叠，两个区间可以无缝连接起来，意味着我们可以把区间[0,miss)扩展到[0, miss+x)
2. 如果数组中不存在小于或等于miss的元素，则区间[0,miss)[x, miss+x) 脱节了，连不起来。此时我们需要添加一个数，最大限度的扩展区间[0, miss)。那添加哪个数呢？当然是添加miss本身，这样区间[0,miss)[miss, miss+miss)恰好可以无缝拼接。

### 代码​

// Patching Array// Time complexity: O(n), Space complexity: O(1)public class Solution {    public int minPatches(int[] nums, int n) {        long miss = 1;        int added = 0;        int i = 0;        while (miss <= n) {            if (i < nums.length && nums[i] <= miss) {                miss += nums[i++];            } else {                miss += miss;                ++added;            }        }        return added;    }}