Tutte le sfide
Facile 1 risolta 100.0% di accettazione

Cash: Fewest Coins

Give change with as few U.S. coins as possible.

Cosa imparerai

  • Pick the largest coin first
  • Use division and remainder for counts
  • See when greedy change is optimal

Problema

Mostra traduzione

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.

Vincoli

0 ≤ cents ≤ 1,000,000

Esempi

Esempio 1
Input:
cents = 41

Output atteso:
expected = 4
Input:
long long cents = 41;

Output atteso:
long long expected = 4;
Input:
long cents = 41;

Output atteso:
long expected = 4;

Spiegazione

One quarter (25), one dime (35), one nickel (40) and one penny (41): 4 coins.

Esempio 2
Input:
cents = 0

Output atteso:
expected = 0
Input:
long long cents = 0;

Output atteso:
long long expected = 0;
Input:
long cents = 0;

Output atteso:
long expected = 0;

Spiegazione

No change is owed: 0 coins.

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Use the largest coin denomination that fits, then move to smaller coins with the remaining amount.

Suggerimento 2

Divide and take remainders to count each coin type efficiently.

Suggerimento 3

Be careful with exact multiples so you do not leave a leftover amount by mistake.

Complessità attesa

O(1) time, O(1) extra space

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

# Programmatore Linguaggio Tempo Memoria Voto dell'IA Soluzione
1 HJhettory Jurash Python 873 ms - 4/5 Vedi il codice

Impara dagli altri

Soluzioni della community

Attenzione spoiler: 1 soluzione completa sotto Prova prima a risolverla da solo. Puoi comunque sbirciare il codice degli altri sviluppatori e le recensioni AI. Accedi e risolvi la sfida per partecipare alla discussione.