Greedy: Add elements in an array so the sum is equal to the given range

Problem Statement:

You are given sorted array, and an integer K.

You need to add elements in such a way that any number in the range [1, k] inclusive can be formed by the sum of the some of the elements in the array.

You need to return the minimum number of patches required

Example

Input: nums = [1,3], k = 6
Output: 1

If we have the array [1, 3], then the combination of the elements are [1], [3], [1, 3] which has the possible sum [1, 3, 4]

If we add 2 to the array, [1, 2, 3], the combination are [1], [2], [3], [1, 3], [2, 3], [1, 2, 3] which has the sum [1, 2, 3, 4, 5, 6] that will cover the range [1, 6]

Solution

We need to use greedy method to solve this problem.

First we will do a dry run, and check what will be the missing number.

For example, if we have empty array:
[] -> [], the next missing number is 1.

[1] -> [1], the next missing number is 2

[1,2] -> [1, 2, 3] the next missing number is 4

[1, 2, 4] -> [1, 2, 3, 4, 5, 6, 7], the next missing value is 8.

From the above example we can see that, if we have 1, we know 1 is patched completely.

if we have [1,2], we know 1..3 is patched completely.

if we have [1,2,3], we know 1..6 is patched completely.

Similarly if we have [1, 2, 3, 9], we must patch a new number so that we dont miss [7,8]. Any number greater than 7 will not help.

So we need to find a number from [1..7]. So if we choose 7, it will patch 1+2+3+7 = 13 completely. Then if we use 9, it will patch till 13+9 = 22 completely.

Similarly we can reach n as soon as possible.

So here the greedy method is to get the as many values as possible.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>

using namespace std;

int min_patches_required(vector<int>& nums, int n) 
{  
  long long sum = 0;
  int i=0;
  int patch = 0;
  
  while(sum < n) 
  {
      if(i>=(int)nums.size() || sum+1 < nums[i]) 
      {
          patch += 1;
          sum = sum + (sum+1);
      }
      else 
      {
          sum = sum + nums[i];
          i++;
      }
  }
  
  return patch;
}

int main()
{
   vector<int>arr = {1, 3};
   int n = 6;

   cout << "The min patches required are = "<<min_patches_required(arr, n)<<endl;
   return 0;
}

Output:

The min patches required are = 1