Условие
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.
Ограничения
1 ≤ number of coins ≤ 200,000. Each value is between 1 and 1,000,000,000.
Примеры
Ввод:
coins = [1, 1, 4]
Ожидаемый вывод:
expected = 3Ввод:
std::vector<long long> coins = {1, 1, 4};
Ожидаемый вывод:
long long expected = 3;Ввод:
long[] coins = new long[] {1, 1, 4};
Ожидаемый вывод:
long expected = 3;Пояснение
Amounts 1 and 2 use the one-valued coins. No available subset totals 3.
Ввод:
coins = [2, 3]
Ожидаемый вывод:
expected = 1Ввод:
std::vector<long long> coins = {2, 3};
Ожидаемый вывод:
long long expected = 1;Ввод:
long[] coins = new long[] {2, 3};
Ожидаемый вывод:
long expected = 1;Пояснение
There is no way to make 1 because every coin is worth at least 2.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Sort the coins and build the smallest reachable sum from smallest upward.
Подсказка 2
If the next coin is larger than the first unreachable amount, that amount can never be formed.
Подсказка 3
Duplicates help only when they extend the currently reachable range without gaps.
Ожидаемая сложность
O(n log n) time, O(1) extra space, excluding sorting implementation details
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.