Problema
Un cassiere dà il resto usando quarti di dollaro (25¢), dime (10¢), nickel (5¢) e penny (1¢). Usare sempre la moneta più grande che non supera il resto da dare garantisce il minor numero di monete per questi valori. Restituisci quante monete sono necessarie per cents.
Implementa fewest_coins(cents).
Input
cents: Il resto dovuto in centesimi.
Output
Restituisci il numero minimo di monete.
Vincoli
0 ≤ cents ≤ 1.000.000
Esempi
Input:
cents = 41
Output atteso:
expected = 4Input:
long long cents = 41;
Output atteso:
long long expected = 4;Input:
long cents = 41;
Output atteso:
long expected = 4;Spiegazione
Un quarto di dollaro (25), una dime (35), un nickel (40) e un penny (41): 4 monete.
Input:
cents = 0
Output atteso:
expected = 0Input:
long long cents = 0;
Output atteso:
long long expected = 0;Input:
long cents = 0;
Output atteso:
long expected = 0;Spiegazione
Nessun resto dovuto: 0 monete.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Usa la moneta di valore più alto che entra, poi passa a monete più piccole con il resto.
Suggerimento 2
Dividi e usa i resti per contare ogni tipo di moneta in modo efficiente.
Suggerimento 3
Fai attenzione ai multipli esatti, così non lasci per errore un resto residuo.
Complessità attesa
tempo O(1), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.