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:

Input: nums = [1,4], n = 7
Output: 1 
Explanation:
Combinations of nums are [1], [4], [1, 4], which form possible sums of: 1, 4, 5.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [1, 2], [4], [1, 4], [2,4], [1,2,4].
Possible sums are 1, 2, 3, 4, 5, 6, 7 which now covers the range [1, 7].
So we only need 1 patch.

Approach:  It's a easy problem to solve. Let's understand the algorithm using an example say our input array is [1, 2, 5, 6, 20] and n = 50.

Let's take the element of array one by one (remember the array is already sorted) and see what is the range it can cover:

1. input[0] = 1 so it can cover range [1 - 1] with number_used = [1], number_added = []
2. input[1] = 2 so it can cover  range 1 -  (1 (previous max) + 2 (current number)) =  [1 - 3] with number_used = [1, 2], number_added = []
3. input[2] = 5  now 5 > 4 (next number to cover) so we need to add a new number to get 4 so let's add 4. After adding 4 it can cover range 1 - (3 + 4) =  [1 - 7] with number_used = [1, 2], number_added = [4]
4. input[2] = 5 and 5 < 8 (next number to cover) so now it can cover range 1 - (7 + 5) =  [1 - 12] with number_used = [1, 2, 5], number_added = [4]
5. input[3] = 6 and 6 < 13(next number to cover) so now it can cover 1 - (12 + 6) = [1, 18] with number_used = [1, 2, 5, 6], number_added = [4]
6. input[4] = 20 and 20 > 19 (next number to cover) so we need to add a new number to get 19. Optimally let's add 19. After adding 19 it can cover range 1 - (18 + 19) =  [1 - 37] with number_used = [1, 2, 5, 6], number_added = [4, 19]
7. input[4] = 20 and 20 < 38 (next number to cover) so now it can cover range 1- (37 + 20) = [1, 57] with number_used = [1, 2, 5, 6, 20], number_added = [4, 19]
8. Now since 57 > n (50) we are done here and we can see the count of numbers added/patched is 2 and that is our answer.

Hopefully our algorithm / approach is clear now and can be understood using the implementation itself. 

Implementation in C#:

        public int MinPatches(int[] nums, int n)

        {

            long maxReach = 0;

            int numOfPatchesRequired = 0;

            int i = 0;

            while (maxReach < n)

            {

                if (i < nums.Length && nums[i] <= maxReach + 1)

                {

                    maxReach += nums[i++];

                }

                else

                {

                    ++numOfPatchesRequired;

                    maxReach += (maxReach + 1);

                }

            }

            return numOfPatchesRequired;

        }

Complexity: O(n)