Problema
Um caixa deve dar troco usando moedas de 25¢ (quarter), 10¢ (dime), 5¢ (nickel) e 1¢ (penny). Sempre usar a maior moeda possível que ainda caiba resulta no menor número de moedas para esses valores. Retorne quantas moedas são necessárias para cents.
Implemente fewest_coins(cents).
Entrada
cents: O valor do troco devido, em centavos.
Saída
Retorne o número mínimo de moedas.
Restrições
0 ≤ cents ≤ 1.000.000
Exemplos
Entrada:
cents = 41
Saída esperada:
expected = 4Entrada:
long long cents = 41;
Saída esperada:
long long expected = 4;Entrada:
long cents = 41;
Saída esperada:
long expected = 4;Explicação
Um quarter (25), um dime (35), um nickel (40) e um penny (41): 4 moedas.
Entrada:
cents = 0
Saída esperada:
expected = 0Entrada:
long long cents = 0;
Saída esperada:
long long expected = 0;Entrada:
long cents = 0;
Saída esperada:
long expected = 0;Explicação
Nenhum troco é devido: 0 moedas.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Use a maior moeda que couber e depois passe para moedas menores com o valor restante.
Dica 2
Divida e pegue os restos para contar cada tipo de moeda com eficiência.
Dica 3
Cuidado com múltiplos exatos para não deixar valor sobrando por engano.
Complexidade esperada
tempo O(1), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.