Patching Array

Problem

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.

Solution

Concise Solution

public class Solution {
    public int minPatches(int[] nums, int n) {
        int end = 1, patch = 0, index = 0;
        while (end > 0 && n >= end) {
            if (index < nums.length && nums[index] <= end) end += nums[index++];
            else {
                end += end;
                patch++;
            }
        }
        return patch;
    }
}

Analysis

We maintain an interval [start, end) which indicates the current cover until end (exclusive)
Ex, if end = 3, we have every sum from 1 until 3 (3 exclusive)
Then as long as n is not in this cover, we continue the loop
Notice that we need to check end > 0 to avoid overflow (end will become negative if exceeds MAX_VALUE)
Then inside the loop, we compare nums[index] and end
This is because we need to make sure our interval has every sum from beginning until end
We use <= because if nums[index] == end, we can construct sum = nums[index] by just having nums[index]
Otherwise, we must have a sum from end, hence we add end to the list
After adding end to the list, the sums will cover [start, end + end) because we have all sums until end before
It's like we need end, and we can add end to every single sum we already have
Therefore, now the cover becomes [start, end + end)
Of course, this is the time we increment the patch cause we add one number which is end