Problema
Você pode selecionar qualquer subconjunto das moedas fornecidas. Cada moeda individual pode ser usada no máximo uma vez, mesmo que haja várias moedas com o mesmo valor. Encontre o menor inteiro positivo que nenhuma seleção de moedas consegue formar.
Implemente missing_coin_sum(coins).
Entrada
coins: Os valores das moedas disponíveis; duplicatas representam moedas distintas.
Saída
Retorne o menor valor positivo impossível de ser formado.
Restrições
1 ≤ número de moedas ≤ 200.000. Cada valor está entre 1 e 1.000.000.000.
Exemplos
Entrada:
coins = [1, 1, 4]
Saída esperada:
expected = 3Entrada:
std::vector<long long> coins = {1, 1, 4};
Saída esperada:
long long expected = 3;Entrada:
long[] coins = new long[] {1, 1, 4};
Saída esperada:
long expected = 3;Explicação
Os valores 1 e 2 podem ser formados usando as moedas de valor 1. Não existe nenhum subconjunto disponível que some 3.
Entrada:
coins = [2, 3]
Saída esperada:
expected = 1Entrada:
std::vector<long long> coins = {2, 3};
Saída esperada:
long long expected = 1;Entrada:
long[] coins = new long[] {2, 3};
Saída esperada:
long expected = 1;Explicação
Não há como formar 1 porque todas as moedas valem pelo menos 2.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Ordene as moedas e construa a menor soma alcançável a partir das menores moedas.
Dica 2
Se a próxima moeda for maior que a menor soma ainda inalcançável, essa soma nunca poderá ser formada.
Dica 3
Duplicatas ajudam só quando estendem o intervalo alcançável atual sem criar lacunas.
Complexidade esperada
O(n log n) time, O(1) extra space, excluding sorting implementation details
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.