Problema
Mostra originale (inglese)Puoi selezionare qualsiasi sottoinsieme delle monete fornite. Ogni singola moneta può essere usata al massimo una volta, anche se ci sono più monete con lo stesso valore. Trova il più piccolo intero positivo che nessuna selezione può produrre.
Implementa missing_coin_sum(coins).
Input
coins: I valori delle monete disponibili; i duplicati rappresentano monete distinte.
Output
Restituisci il più piccolo importo positivo impossibile.
Vincoli
1 ≤ numero di monete ≤ 200.000. Ogni valore è compreso tra 1 e 1.000.000.000.
Esempi
Esempio 1
Input:
coins = [1, 1, 4]
Output atteso:
expected = 3Input:
std::vector<long long> coins = {1, 1, 4};
Output atteso:
long long expected = 3;Input:
long[] coins = new long[] {1, 1, 4};
Output atteso:
long expected = 3;Spiegazione
Gli importi 1 e 2 si ottengono usando le monete di valore uno. Nessun sottoinsieme disponibile totalizza 3.
Esempio 2
Input:
coins = [2, 3]
Output atteso:
expected = 1Input:
std::vector<long long> coins = {2, 3};
Output atteso:
long long expected = 1;Input:
long[] coins = new long[] {2, 3};
Output atteso:
long expected = 1;Spiegazione
Non è possibile ottenere 1 perché ogni moneta vale almeno 2.
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.