Jak poznać najmniejszą liczbę, którą powinniśmy dodać, aby uzyskać pełną tablicę

Question

ostatnio spotkałem się z pytaniem takim jak:
Założono, że masz int N, a także masz int [] i każdy element w tej tablicy może tylko być użyty raz. Musimy zaprojektować algorytm, aby uzyskać od 1 do N, dodając te liczby i ostatecznie zwracając najmniejsze liczby, które musimy dodać.
Na przykład:

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. 

myślę o rozwiązywaniu tego za pomocą DFS. Czy masz lepsze rozwiązania? Dzięki!

Answer 1

Oto wyjaśnienie, dlaczego rozwiązanie, które opublikował OP, działa (algorytm, krótko, to przemieszczenie posortowanych istniejących elementów, gromadzenie sumy poprzednich istniejących elementów i dodanie elementu do tablicy i suma, jeśli to zrobi nie istnieje i przekracza aktualną sumę):

Pętla testuje w kolejności każdy element, który musi zostać uformowany i sumuje poprzednie elementy. Informuje nas, czy potrzebny jest element, który jest większy niż obecna suma. Jeśli myślisz o tym, to jest naprawdę proste! Jak moglibyśmy stworzyć ten element, gdy użyliśmy już wszystkich poprzednich elementów, co stanowi suma!

W przeciwieństwie do tego, skąd wiemy, że wszystkie elementy pośrednie będą mogły być tworzone, gdy suma jest większa niż bieżący element? Na przykład, rozważmy 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) 

Q.E.D. 

Answer 2

Nie wiem, czy jest to dobre rozwiązanie, czy nie:

Chciałbym utworzyć drugą tablicę array (Boolean) z zapamiętaniem wszystkich numerów mogę obliczyć. Potem napisałbym metodę symulującą dodanie numeru do tablicy. (W twoim przykładzie 1, 3 i 2 są dodawane do tablicy). Tablica boolowska zostanie zaktualizowana, aby zawsze pamiętać, które wartości (liczby) można obliczyć za pomocą dodanych liczb.

Po wywołaniu metody dodawania na początkowych wartościach macierzy, należy przetestować każdy numer x (1 < = x < = N), jeśli można obliczyć x. Jeśli nie, wywołaj metodę dodawania dla x.

ponieważ moje wyjaśnienie nie jest dobre dodam (niesprawdzone) kod Java:

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

Edycja: Testowany kod i zmienił niektóre błędy (ale rozwiązanie Rachel wydaje się być lepszy w każdym razie)

Answer 3

It jest znanym problemem z programowania dynamicznego. Można odwołać się do kompletnego rozwiązania tutaj https://www.youtube.com/watch?v=s6FhG--P7z0

Answer 4

Właśnie znalazłem możliwe rozwiązanie jak ten

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

I przetestować niektóre przypadki i wygląda poprawne. Ale ten, który to napisał, nie dał nam żadnych wskazówek i jestem naprawdę zdezorientowany tym. Czy ktoś może wymyślić jakieś wyjaśnienia? Dzięki!