Tutte le sfide
Facile 1 risolta 100.0% di accettazione

Contanti: Il Minor Numero di Monete

Dai il resto usando il minor numero possibile di monete statunitensi.

Cosa imparerai

  • Scegliere prima la moneta più grande
  • Usare divisione e resto per le quantità
  • Sapere quando il resto greedy è ottimale

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

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

Un quarto di dollaro (25), una dime (35), un nickel (40) e un penny (41): 4 monete.

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

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.

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.