[Algorithm] Patching Array

Patching Array

Problem Statment:

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.

Solution: Greedy + Math

This problem seems to be astonishingly hard at first glance. If you're ever thinking about enumerating all possible combination, time complexity will easily explode. Indeed this cannot be solved by brutal force.

Now let's consider what it means by this statement:

"any number in range [1, n] inclusive can be formed by the sum of some elements in the array"

This means a requirement of the problem statement of course, but there's more to it, it is also telling us one property. Suppose we have an array which contains combinations that sum up to each and every element in range [1, n], then it also means if we add an element with value equal to n+1, we could extend the range to [1, n+n+1]. Why is that? See following, I use C[i] to represent one combination that can add up to number i.

For range [1, n] we have:

C[1] = 1, C[2] = 2, C[3] = 3, ..., C[i] = i, ... C[n] = n

Now if we add one more element n+1 to this sequence we will have:

C[1] = 1, C[2] = 2, C[3] = 3, ..., C[i] = i, ... C[n] = n, C[0] + n+1 = n+1, C[1] + n+1 = n+2, ..., C[i] + n+1 = i+n+1, ... C[n] + n+1 = n+n+1

This property is the key to solve this problem. Now let's call the range we have reached as consolidated_range. At the beginning we have consolidated range as 0, which also implies we don't have any elements in the array yet. As we go along the input array, we are adding elements into the final sequence and as a result we are extending our consolidated_range. Then we could have the following two possibilities:

1. The consolidated_range can connect with one element nums[i] in the array (connect means consolidated_range+1 >= nums[i]). In this case, the consolidated_range we be extended by nums[i] according to the property we described. Also we don't consider this as a patch because element is in the original array.

2. The consolidated_range cannot connect with the element nums[i] or there's no element left. This would imply a patch and the optimal patch we can use is to add an number with value of consolidated_range+1, because every value below consolidated_range+1 has combination that sums up to it and according to the property we extend our range to consolidated_range + consolidated_range + 1.

We will keep extending the consolidated range until it hits the target range. Code implementation as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { public: int minPatches(vector<int>& nums, int n) { long long consolidated = 0; int len = nums.size(); int i=0; int count=0; /* consolidated means we can sum up to every value in [1, consolidated] * 1) When nums[i] is below or equal consolidated or equal to consolidated+1 * we can extend the consolidated by nums[i], because if we can reach nums[i] * without nums[i] itself, we can also reach consolidated + nums[i] * * * 2) When consolidated is below nums[i], then we need an optimal number which is * equal to consolidated+1, because we can then use consolidated+1 as the base and * use any combination to reach (consolidated+consolidated+1) * */ while (consolidated < n) { if (i < len && nums[i] <= consolidated+1) { consolidated += nums[i++]; } else { consolidated += (consolidated+1); count++; } } return count; } };