Problème
A cashier gives change using quarters (25¢), dimes (10¢), nickels (5¢) and pennies (1¢). Always using the largest coin that still fits gives the fewest coins for these values. Return how many coins are needed for cents.
Implement fewest_coins(cents).
Input
cents: The change owed in cents.
Output
Return the minimum number of coins.
Contraintes
0 ≤ cents ≤ 1,000,000
Exemples
Entrée :
cents = 41
Sortie attendue :
expected = 4Entrée :
long long cents = 41;
Sortie attendue :
long long expected = 4;Entrée :
long cents = 41;
Sortie attendue :
long expected = 4;Explication
One quarter (25), one dime (35), one nickel (40) and one penny (41): 4 coins.
Entrée :
cents = 0
Sortie attendue :
expected = 0Entrée :
long long cents = 0;
Sortie attendue :
long long expected = 0;Entrée :
long cents = 0;
Sortie attendue :
long expected = 0;Explication
No change is owed: 0 coins.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Utilise la plus grande valeur de pièce qui rentre, puis passe à des pièces plus petites avec le montant restant.
Indice 2
Divise et prends les restes pour compter efficacement chaque type de pièce.
Indice 3
Fais attention aux multiples exacts pour ne pas laisser un reste par erreur.
Complexité attendue
temps O(1), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.