Problem
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.
Einschränkungen
0 ≤ cents ≤ 1,000,000
Beispiele
Eingabe:
cents = 41
Erwartete Ausgabe:
expected = 4Eingabe:
long long cents = 41;
Erwartete Ausgabe:
long long expected = 4;Eingabe:
long cents = 41;
Erwartete Ausgabe:
long expected = 4;Erläuterung
One quarter (25), one dime (35), one nickel (40) and one penny (41): 4 coins.
Eingabe:
cents = 0
Erwartete Ausgabe:
expected = 0Eingabe:
long long cents = 0;
Erwartete Ausgabe:
long long expected = 0;Eingabe:
long cents = 0;
Erwartete Ausgabe:
long expected = 0;Erläuterung
No change is owed: 0 coins.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Nimm die größte Münzdenomination, die passt, und gehe dann mit dem Restbetrag zu kleineren Münzen über.
Hinweis 2
Nutze Division und Rest, um jeden Münztyp effizient zu zählen.
Hinweis 3
Achte auf exakte Vielfache, damit du nicht versehentlich einen Restbetrag übrig lässt.
Erwartete Komplexität
Zeit O(1), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.