330. Patching Array 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minPatches(int[] nums, int n) {
        int minAdd = 0;
        int i = 0;
        long start = 1; // range: [0, start - 1]
        while (start - 1 < n) {
            if (i < nums.length && nums[i] <= start) { // 当 nums[i] 小于等于 start 时，之前的 [0, start - 1] 区间与加上 nums[i] 后的新区间 [coins[i], start - 1 + nums[i]] 可以合并
                start += nums[i];
                i++;
            } else {
                start += start; // 添加一个 start
                minAdd++;
            }
        }

        return minAdd;
    }
}

References

330. Patching Array