Problème
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.
Contraintes
1 ≤ number of coins ≤ 200,000. Each value is between 1 and 1,000,000,000.
Exemples
Entrée :
coins = [1, 1, 4]
Sortie attendue :
expected = 3Entrée :
std::vector<long long> coins = {1, 1, 4};
Sortie attendue :
long long expected = 3;Entrée :
long[] coins = new long[] {1, 1, 4};
Sortie attendue :
long expected = 3;Explication
Amounts 1 and 2 use the one-valued coins. No available subset totals 3.
Entrée :
coins = [2, 3]
Sortie attendue :
expected = 1Entrée :
std::vector<long long> coins = {2, 3};
Sortie attendue :
long long expected = 1;Entrée :
long[] coins = new long[] {2, 3};
Sortie attendue :
long expected = 1;Explication
There is no way to make 1 because every coin is worth at least 2.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Sort the coins and build the smallest reachable sum from smallest upward.
Indice 2
If the next coin is larger than the first unreachable amount, that amount can never be formed.
Indice 3
Duplicates help only when they extend the currently reachable range without gaps.
Complexité attendue
O(n log n) time, O(1) extra space, excluding sorting implementation details
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.