Problem

Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.

Return the minimum number of patches required.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].

Example 3:

1
2

Input: nums = [1,2,2], n = 5
Output: 0

Solution

Method 1 - Greedy

Note that, we should construct all numbers from 1 to n. A dirty take on this problem would be to to go from 1 to n and add all the numbers missing in the array. But certainly this is not the optimal solution. Because we don’t actually need all consecutive numbers to get another by adding them up.

For example, nums = [1, 2, 4]. n = 3, in this case we don’t need 3 to make 3 because we can make 3 by adding 1 and 2. numPatches = 0 n = 5 , we don’t need 5 either, because we can make 5 by adding 1 and 4. numPatches = 0 n = 8, now, we need to add 8 to the list. numPatches = 1. Once we added 8 to the list i.e. nums'=[1, 2, 4, 8] then we don’t need to add any more element until 15 (why?).

Basically, as long as cumulative sum, lets call it maxReach, is greater than the number we need to create , we are good. For instance, if you can make all sums up to 5, and you have a 3 in your set, you can now make all sums up to 8.

But if maxReach falls below the current number (between 1 to n) we need to create , then we have to add the current cumulative sum to itself (why?). If there is a gap, meaning the next number nums[i] is greater than maxReach, we can’t extend the coverage with our existing numbers because you have no way to form maxReach.

This is because we assumed at any particular time maxReach is equal or greater than the current element we need to create. That is we doubling the maxReach when we add a missing element. By always choosing maxReach as the patch when there’s a gap, we are making the greedy choice that gives the smallest next number to cover the widest possible range. Lets look at example below:

  • Let’s say maxReach is 4, meaning we can form sums 1, 2, 3.
  • If we patch and add 4, our new maxReach becomes 8.
  • We can now create sums 4 (patched number), 5 (1 + 4), 6 (2 + 4), 7 (3 + 4) in addition to our original 1, 2, 3.

Any number larger than maxReach would leave a gap. For eg.

  • Let’s say maxReach is 4, meaning we can form sums 1, 2, 3.
  • If we patch and add 8, our new maxReach becomes 12.
  • We can now create sums 8 (patched number), 9 (1 + 8), 10 (2 + 8), 11 (3 + 8) in addition to our original 1, 2, 3. So, it create the gaps: 4, 5, 6, 7. Any smaller wouldn’t be possible since all numbers up to maxReach are already covered.

Algorithm

Here’s the step-by-step approach:

  1. Initialize maxReach to 1, since we need to start forming sums from 1.
  2. Initialize a variable patches to 0, which will store the result - the minimum number of patches required.
  3. Iterate through the array nums, and for each number till maxReach <= n:
    • While maxReach is less than nums[i], patch the array with maxReach and increment patches and maxReach accordingly.
    • Otherwise, update maxReach to include the current number nums[i] in the sum to form other numbers.
  4. If we reach the end of the array and maxReach is still less than n, we continue adding patches (maxReach + 1) until maxReach is at least n.

Code

1
2


##### Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public class Solution {

	public int minPatches(int[] nums, int n) {
		long maxReach = 1; // Use long to prevent integer overflow
		int patches = 0;
		int i = 0;

		while (maxReach <= n) {
			if (i < nums.length && nums[i] <= maxReach) {
				maxReach += nums[i];
				i++;
			} else {
				maxReach += maxReach; // Patch the array with this number
				patches++; // Increase the count of patches used
			}
		}

		return patches;
	}
}

Dry Run

Initial Setup
  • nums = [1, 2, 5, 6, 20] and n = 50.
  • maxReach = 1 (maximum sum that can be formed)
  • patches = 0 (count how many numbers we need to patch)
  • i = 0 (index into the nums array)
Iteration 1
  • Since nums[0] = 1, and is in the maxReach boundary
  • So, we increment the maxReach to 2.
Iteration 2
  • Moving to nums[1] = 2, we add it to our range since 2 <= maxReach.
  • Update maxReach = 2 + 2 = 4.
Iteration 3
  • Next, nums[2] = 5. Since 5 > maxReach, we cannot include it yet.
  • We must patch the set first to continue forming all numbers up to n.
  • We add 4 as the patch, and now we can achieve up to maxReach + 4 = 8. Update maxReach = 8.
Iteration 4
  • Since nums[2] = 5 <= maxReach, it can now be included. Update maxReach = 8 + 5 = 13.
Iteration 5
  • nums[3] = 6 is already covered by the range [1, 13] since 6 < 13. We add it to maxReach → maxReach = 13 + 6 = 19.
Iteration 6
  • nums[4] = 20 cannot be used immediately since 20 > 19. We have to patch the set first.
  • Add a patch 19 to fill the gap. Update maxReach = 19 + 19 = 38.
Iteration 7
  • Now we can include nums[4] = 20 because 20 <= 38. Update maxReach = 38 + 20 = 58.
End

Since maxReach is now 58, which is greater than n, and we have used 2 patches (4 and 19), the iteration ends here, and the code will return 2 as the minimum number of patches required. These patches have allowed us to form all numbers from 1 to 50 using the given nums array and the patches.