Patching Array

Problem Statement

The task at hand involves working with a sorted integer array, named nums, and a target range defined by the integer n. The objective is to make sure that every integer from 1 to n can be formed by summing up some subset of elements from this array. If required, you have the ability to add or "patch" new numbers into the array to achieve this objective.

The main problem is to determine the minimum number of patches required so that any number within the range [1, n] can be formed using sums of the elements, whether original or added, in the modified array. This is all about strategically adding minimal elements to cover any possible gaps within the specified range.

Examples

Example 1

Input:

nums = [1,3], n = 6

Output:

1
Explanation:
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

Input:

nums = [1,5,10], n = 20

Output:

2
Explanation: The two patches can be [2, 4].

Example 3

Input:

nums = [1,2,2], n = 5

Output:

0

Constraints

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 104
• nums is sorted in ascending order.
• 1 <= n <= 231 - 1

Approach and Intuition

The central idea of this problem can be dissected through simple examples, which reveal strategies using a greedy algorithm approach.

1. Start considering the smallest number in the range, which is 1.
2. Using the sorted nature of nums, calculate the smallest sum not representable given the current state of nums. If this sum, x, is within [1, n] and x is not immediately coverable with existing sums or elements in nums, add x to nums.
3. This greedily chosen x will always be the smallest missing sum because if we can sum every number up to x-1, adding x ensures that all sequences up to x + (x-1) are now also possible.
4. Repeat this process until all numbers through n are coverable by sums of elements in nums.

Analyzing Examples:

• Example 1: Start with [1, 3] and target n = 6.

  • Sums initially possible: 1, 3, 4.
  • 2 is the smallest missing sum, so add it.
  • After patch, sums from 1 to 6 are all possible, hence 1 patch.

• Example 2: Start with [1, 5, 10] and target n = 20.

  • Initially coverable: 1, then notice missing 2.
  • Adding 2 leads to inability to make 4 next, so add 4.
  • Successive sums and checks ensure coverage up to 20, totaling 2 patches.

• Example 3: Provided [1, 2, 2] with n = 5.

  • Already possible to make all sums from 1 to 5 with existing numbers, so 0 patches.

The examples hint at a systematic procedure where one identifies gaps in the range achieveable by existing subsets and patches optimally by filling the smallest gap each time. This method ensures the minimal additions required to complete the range [1, n].

Solutions

public class Solution {
    public int calculatePatches(int[] array, int target) {
        int patchCount = 0, idx = 0;
        long maxReachable = 1;
        while (maxReachable <= target) {
            if (idx < array.length && array[idx] <= maxReachable) {
                maxReachable += array[idx++];
            } else {
                maxReachable += maxReachable;
                patchCount++;
            }
        }
        return patchCount;
    }
}