Problem
Du kannst beliebige Teilmengen der gegebenen Münzen auswählen. Jede einzelne Münze darf höchstens einmal verwendet werden, auch wenn mehrere Münzen denselben Wert haben. Finde die kleinste positive ganze Zahl, die durch keine Auswahl gebildet werden kann.
Implementiere missing_coin_sum(coins).
Eingabe
coins: Die Werte der verfügbaren Münzen; Duplikate stehen für verschiedene Münzen.
Ausgabe
Gib den kleinsten positiven unmöglichen Betrag zurück.
Einschränkungen
1 ≤ Anzahl der Münzen ≤ 200.000. Jeder Wert liegt zwischen 1 und 1.000.000.000.
Beispiele
Eingabe:
coins = [1, 1, 4]
Erwartete Ausgabe:
expected = 3Eingabe:
std::vector<long long> coins = {1, 1, 4};
Erwartete Ausgabe:
long long expected = 3;Eingabe:
long[] coins = new long[] {1, 1, 4};
Erwartete Ausgabe:
long expected = 3;Erläuterung
Die Beträge 1 und 2 können mit den Einser-Münzen gebildet werden. Keine verfügbare Teilmenge ergibt 3.
Eingabe:
coins = [2, 3]
Erwartete Ausgabe:
expected = 1Eingabe:
std::vector<long long> coins = {2, 3};
Erwartete Ausgabe:
long long expected = 1;Eingabe:
long[] coins = new long[] {2, 3};
Erwartete Ausgabe:
long expected = 1;Erläuterung
Es gibt keine Möglichkeit, 1 zu bilden, da jede Münze mindestens den Wert 2 hat.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Sortiere die Münzen und baue die kleinste erreichbare Summe von klein nach groß auf.
Hinweis 2
Wenn die nächste Münze größer ist als der erste nicht erreichbare Betrag, kann dieser Betrag nie gebildet werden.
Hinweis 3
Duplikate helfen nur, wenn sie den aktuell erreichbaren Bereich ohne Lücken erweitern.
Erwartete Komplexität
O(n log n) time, O(1) extra space, excluding sorting implementation details
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.