How to find out the smallest number of numbers we need to add in order to get a full array

Question

I recently met this question:
Suppose you have int N, and you also have int [], and each element in this array can be used only once. And we need to develop an algorithm to get from 1 to N by adding these numbers and finally returning the smallest numbers we need to add.
For instance:

N = 6, array is [1,3] 1 : we already have. 2 : we need to add it to the array. 3 : we can get it by doing 1 + 2. 4: 1 + 3. 5 : 2 + 3. 6 : 1 + 2 + 3. So we just need to add 2 to our array and finally we return 1. 

I think about it using DFS. Do you have some better solutions? Thanks!

Answer 1

It explains why the OP solution is placed (the algorithm, in short, must cross the sorted existing elements, save the accumulated sum of the previous existing elements and add the element to the array and sum if it does not exist and exceed the current amount):

The loop checks the order of each element to be formed and sums up the previous elements. He warns us if an item is required that is larger than the current amount. If you think about it, it is very simple! How can we create an element when we have already used all the previous elements, what is the sum?

In contrast to this, how do we know that all intermediate elements can be formed when the sum is larger than the current element? For example, consider n = 7, a = {} :

 The function adds {1,2,4...} So we are up to 4 and we know 1,2,3,4 are covered, each can be formed from equal or lower numbers in the array. At any point, m, in the traversal, we know for sure that X0 + X1 ... + Xm make the largest number we can make, call it Y. But we also know that we can make 1,2,3...Xm Therefore, we can make Y-1, Y-2, Y-3...Y-Xm (In this example: Xm = 4; Y = 1+2+4 = 7; Y-1 = 6; Y-2 = 5) QED 

Answer 2

I don't know if this is a good solution or not:

I would create a second array (a logical array), storing all the numbers that I can calculate. Then I will write a method that simulates adding a number to an array. (In your example, 1, 3, and 2 are added to the array). The Boolean array will be updated to always remember which values ​​(numbers) can be calculated with the numbers added.

After calling the add method on the initial values ​​of the array, you check each x number (1 <= x <= N) if x can be calculated. If you do not call the add method for x.

since my explanation is not suitable, I will add (unverified) Java code:

 static int[] arr = {3,5}; static int N = 20; //An Array remembering which values can be calculated so far static boolean[] canCalculate = new boolean[N]; //Calculate how many numbers must be added to the array ( Runtime O(N^2) ) public static int method(){ //Preperation (adding every given Number in the array) for(int i=0; i<arr.length; i++){ addNumber(arr[i]); } //The number of elements added to the initial array int result = 0; //Adding (and counting) the missing numbers (Runtime O(N^2) ) for(int i=1; i<=N; i++){ if( !canCalculate[i-1] ){ addNumber(i); result++; } } return result; } //This Method is called whenever a new number is added to your array //runtime O(N) public static void addNumber( int number ){ System.out.println("Add Number: "+(number)); boolean[] newarray = new boolean[N]; newarray[number-1] = true; //Test which values can be calculated after adding this number //And update the array for(int i=1; i<=N; i++){ if( canCalculate[i-1] ){ newarray[i-1] = true; if( i + number <= N ){ newarray[i+number-1] = true; } } } canCalculate = newarray; } 

Edit: tested the code and changed some errors (but the rachel solution seems to be better anyway)

Answer 3

This is a known dynamic programming problem. You can refer to the complete solution here https://www.youtube.com/watch?v=s6FhG--P7z0

Answer 4

I just found a possible solution like this

  public static int getNum(int n, int[] a) { ArrayList<Integer> output = new ArrayList<Integer>(); Arrays.sort(a); int sum = 0; int i = 0; while(true) { if (i >= a.length || a[i] > sum + 1) { output.add(sum + 1); sum += sum + 1; } else { sum += a[i]; i++; } if (sum >= n) { break; } } return output.size(); }; 

And I check some cases, and it looks right. But the one who writes this has not given us any hints, and I am really embarrassed by this. Can anyone come up with some kind of explanation? Thanks!