Patching Array

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.

This is a Leetcode problem.

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.

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, A=[1,2,4]. In this case we don’t need 3 to make 3 because we can make 3 by adding 1 and 2. Also we don’t need 5 either. But if we want to make 8 then we have to add 8 in the list. Once we added 8 to the list i.e. A’=[1,2,4,8] then we don’t need to add any more element until 15 (why?).

Basically, as long as cumulative sum so far is greater than the number we need to create , we are good. But id cumsum falls below the current number (between 1 to n) we need to create , then we have to add the current cumsum to itself (why?). This is because we assumed at any particular time cumsum is equal or greater than the current element we need to create. That is we doubling the cumsum when we add a missing element.

Below is the implementation of the above idea in O(n) time and O(1) space.

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