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

Let A be the collection of input numbers.

Initialize a boolean array B to store in B[i] whether or not we can 'make' i by adding the numbers in A as described in the problem. Make all B[i] initially FALSE.

Then, pseudocode:

for i = 1 to N

     if B[i] && (not A.Contains(i))
        continue next i

      if not A.Contains(i)
        countAdded++

      for j = N-i downTo 1
        if B[j] then B[j+i] = TRUE

      B[i] = TRUE

    next i

Explanation:

Within the (main) loop (i): B contains TRUE for the values that we can construct with the values in A that are lower than i. Initially, therefore, with i=1 all B are FALSE.

Then, for each i we have two aspects to consider: (a) is B[i] already TRUE? If not we'll have to add i; (b) is i present in A? because, see previous remark, at this point we haven't yet processed that A-value. So, even if B[i] is already TRUE we'll have to flag TRUE for all (other) B that we may reach with i.

Consequently:

For each i we first determine if either of these two cases applies, and if not, we skip to the next i.

Then, if A does NOT (yet) contain i, it must be the case that B[i] is FALSE, see skip-condition, and therefore we'll add i (to A, conceptually, but it's not necessary to actually put it into A).

Next, either we had i in A initially, or we have just added it. In any case, we'll need to flag B TRUE for all values that can be constructed with this new i. To do so, we better scan existing B in downward fashion; otherwise we may add i to a "new" B-value that has i already as constituent.

Finally, B[i] itself is set TRUE (it may already be TRUE...), simply because i is in A (orginally, or by adding)

Answer 2

For each number starting from 1 we may either

1. Have it in the arr. In such case we update the list of numbers we can make.

2. Don't have it in the arr but we can form it with existing numbers. We simply ignore it.

3. We don't have it in the arr and we cannot form it with existing numbers. We add it to the arr and update the list of numbers we can make.

   For example:
   
   N=10, arr = [1, 2, 6] 
   
   1 is already in arr. 
   
   2 is already in arr. 
   
   3 = 1 + 2
   
   3 is not in the arr but we can already form 3.
   
   4 is not present in arr and we cannot form 4 either with existing numbers.
   So add 4 to the arr and update.
   
   5 = 1 + 4
   
   6 = 2 + 4
   
   7 = 1 + 2 + 4
   
   5 is not in arr but we can form 5. 
   
   6 is in array. So update
   
   8 = 2 + 6
   
   9 = 1 + 2 + 6
   
   10 = 4 + 6
   
   So we return 1 since we only need to add one element which is 4.
   

And following might be an implementation:

int calc(bool arr[], bool can[], int N) {
    // arr[i] is true if we already have number 
    // can[i] is true if we have been able to form number i

    int count=0;
    for(int i=1;i<=N;i++) {
        if(arr[i]==false && can[i]==true) {  // case 1
            continue;
        } else if(arr[i]==false && can[i]==false) {  // case 3
            count++;
        }
        for(int j=N-i;j>=1;j--) {  // update for case 1 and case 3
            if(can[j]==true) can[i+j]=true;
        }
        can[i]=1;
    }
    return count;
}

Answer 3

• Sort the array (NLogN)
• Think this should work -

max_sum = 0
numbers_added = 0 # this will contain you final answer
for i in range(1, N+1):
    if i not in arr and i > max_sum:
        numbers_added += 1
        max_sum += i
    elif i < len(arr):
        max_sum += arr[i]
print numbers_added

Answer 4

One way can be to make a set of all possible numbers that can be generated by the array. This can be done in O(n^2) time. Then, check whether numbers from 1 to n are present in the set in O(1) time. If a number is not present, add it to the count of least adding numbers which was initially zero and make a new empty set. Take all elements of previous set and add not present number to them and add them (set-add method) to the new set. Replace original set with the union of original and new set. Doing this from 1 to n will give the sum of least adding numbers in O(n^3) time.

Answer 5

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;
}