Problem
You may select any subset of the supplied coins. Each individual coin may be used at most once, even when multiple coins share a value. Find the smallest positive integer amount that no selection can produce.
Implement missing_coin_sum(coins).
Input
coins: The values of the available coins; duplicates represent separate coins.
Output
Return the smallest positive impossible amount.
Einschränkungen
1 ≤ number of coins ≤ 200,000. Each value is between 1 and 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
Amounts 1 and 2 use the one-valued coins. No available subset totals 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
There is no way to make 1 because every coin is worth at least 2.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Sort the coins and build the smallest reachable sum from smallest upward.
Hinweis 2
If the next coin is larger than the first unreachable amount, that amount can never be formed.
Hinweis 3
Duplicates help only when they extend the currently reachable range without gaps.
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.