330. 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

Consider [1,2,4,11,30]

with 1,2,4, we can represent [1...7], but 8 cannot, so patch 8, after patch 8, the entire array can represent [1...15], can the patched array combine to 16 ? anwser is yes, [1...15] + 11 can represent up to 26, so no need to add 16 or any number before 27, then just same as patching 8, we need to patch 27, now the entire array can combine to 53, which is > 50, so only need to patch 2 numbers.

why the missing has to be long ?

cause missing += nums[i], missing+=missing, may overflow(for int). 
which will cause the while loop never ends

public class Solution {
    public int minPatches(int[] nums, int n) {
        int count = 0;
        long missing = 1; // before missing number, all numbers can be combined.
                // has to be long, cause missing+=missing or missing += nums[i] may overflow when missing is int.
        int i = 0;
        while(missing <= n){
            if( i < nums.length && nums[i] <= missing ){
                missing += nums[i];// now I can sum up to missing+nums[i] - 1, next missing .
                i++;
            }else{
                missing += missing; // next missing number. 
                count++;
            }
        }

        return count;
    }
}