Problema
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
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.
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.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Ordina le monete e costruisci la somma minima raggiungibile partendo dalla più piccola.
Suggerimento 2
Se la moneta successiva è più grande del primo importo non raggiungibile, quell'importo non potrà mai essere formato.
Suggerimento 3
I duplicati aiutano solo se estendono l'intervallo raggiungibile attuale senza buchi.
Complessità attesa
O(n log n) time, O(1) extra space, excluding sorting implementation details
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.