Вы можете выбрать любой поднабор из предоставленных монет. Каждая отдельная монета может быть использована не более одного раза, даже если несколько монет имеют одинаковый номинал. Найдите наименьшее положительное целое число, которое невозможно получить ни одним выбором монет.
Реализуйте функцию missing_coin_sum(coins).
Входные данные
coins: номиналы доступных монет; одинаковые значения означают разные монеты.
Выходные данные
Верните наименьшую положительную сумму, которую невозможно получить.
Ограничения
1 ≤ количество монет ≤ 200 000. Каждый номинал — от 1 до 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;Пояснение
Суммы 1 и 2 можно получить с помощью монет номиналом 1. Ни один доступный поднабор не дает сумму 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;Пояснение
Получить сумму 1 невозможно, так как каждая монета стоит не менее 2.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Отсортируйте монеты и стройте минимальную достижимую сумму от меньших к большим.
Подсказка 2
Если следующая монета больше, чем первое недостижимое значение, это значение уже никогда не получится собрать.
Подсказка 3
Дубликаты помогают только тогда, когда расширяют текущий достижимый диапазон без пробелов.
Ожидаемая сложность
O(n log n) по времени, O(1) доп. памяти, без учёта деталей реализации сортировки
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.