Patching Array

nums = [1, 3], n = 6 Return 1. Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3,

1. 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].

• Time: O(n)
• Space: O(1)

public int minPatches(int[] nums, int n) {
    long miss = 1;
    int count = 0, i = 0;
    while (miss <= n) {
        if (i < nums.length && nums[i] <= miss) {
            miss += nums[i++];
        } else {
            miss <<= 1;
            count++;
        }
    }
    return count;
}