the least adding numbers--algorithm

Question

I came across this problem online.

Given an integer:N and an array int arr[], you have to add some elements to the array so that you can generate from 1 to N by using (add) the element in the array.

Please keep in mind that you can only use each element in the array once when generating a certain x (1<=x<=N). Return the number of the least adding numbers.

For example:

N=6, arr = [1, 3] 

1 is already in arr. 

add 2 to the arr. 

3 is already in arr 

4 = 1 + 3 

5 = 2 + 3 

6 = 1 + 2 + 3 

So we return 1 since we only need to add one element which is 2.

Can anyone give some hints?

Answer 1

N can always be made by adding subset of 1 to N - 1 numbers except N = 2 and N = 1. So, a number X can must be made when previous 1 to X - 1 consecutive elements are already in the array. Example -

    arr[] = {1, 2, 5}, N = 9
    ans := 0
    1 is already present.
    2 is already present.
    3 is absent. But prior 1 to (3 - 1) elements are present. So 3 is added in the array. But as 3 is built using already existed elements, so answer won't increase.
    same rule for 4 and 5

    So, ans is 0

    arr[] = {3, 4}, for any N >= 2

    ans = 2

    arr[] = {1, 3}, for any N >= 2

    ans = 1

So, it seems that, if only 1 and 2 is not present in the array, we have to add that element regardless of the previous elements are already in array or not. All later numbers can be made by using previous elements. And when trying to making any number X (> 2), we will already found previous 1 to X - 1 elements in the array. So X can always be made.

So, basically we need to check if 1 and 2 is present or not. So answer of this problem won't be bigger than 2

Constraint 2

In above algorithm, we assume, when a new element X is not present in the array but it can be made using already existed elements of the array, then answer won't increase but X will be added in the array to be used for next numbers building. What if X can't be added in the array?

Then, Basically it will turn into a subset sum problem. For every missing number we have to check if the number can be made using any subset of elements in the array. Its a typical O(N^2) dynamic programming algorithm.

int subsetSum(vector<int>& arr, int N)
{
    // The value of subset[i][j] will be true if there is a subset of set[0..j-1]
    //  with sum equal to i
    bool subset[N + 1][arr.size() + 1];

    // If sum is 0, then answer is true
    for (int i = 0; i <= arr.size(); i++)
      subset[0][i] = true;

    // If sum is not 0 and set is empty, then answer is false
    for (int i = 1; i <= N; i++)
      subset[i][0] = false;

     // Fill the subset table in botton up manner
     for (int i = 1; i <= N; i++)
     {
       for (int j = 1; j <= arr.size(); j++)
       {
         subset[i][j] = subset[i][j - 1];
         if (i >= set[j - 1])
           subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1];
       }
     }

     unordered_map<int, bool> exist;
     for(int i = 0; i < arr.size(); ++i) {
         exist[arr[i]] = true;
     }

     int ans = 0;
     for(int i = 1; i <= N; ++i) {
          if(!exist[i] or !subset[i][arr.size()]) {
              ans++;
          }
     }

     return ans;
}