Problema
Ad ogni passo, scegli una cifra decimale non nulla attualmente presente nel numero e sottrai quella cifra. Le cifre vengono prese dal nuovo valore dopo ogni passo. Trova il numero minimo di passi necessari per arrivare a zero.
Implementa removing_digits(n).
Input
n: Il numero iniziale positivo.
Output
Restituisci il minor numero di passi di sottrazione.
Vincoli
1 ≤ n ≤ 1.000.000. Sottrarre zero non è una mossa utile ed è escluso.
Esempi
Input:
n = 14
Output atteso:
expected = 3Input:
long long n = 14;
Output atteso:
long long expected = 3;Input:
long n = 14;
Output atteso:
long expected = 3;Spiegazione
14 → 10 → 9 → 0 richiede tre passi. Nessuna delle possibili prime sottrazioni permette di arrivare a zero in soli due passi.
Input:
n = 7
Output atteso:
expected = 1Input:
long long n = 7;
Output atteso:
long long expected = 1;Input:
long n = 7;
Output atteso:
long expected = 1;Spiegazione
Sottrai l'unica cifra, 7, per arrivare subito a 0.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Ogni numero dipende dalla migliore risposta per numeri più piccoli ottenibili sottraendo una cifra.
Suggerimento 2
La programmazione dinamica su tutti i valori fino a n evita lavoro ripetuto.
Suggerimento 3
Ricorda che le cifre disponibili cambiano dopo ogni sottrazione, e lo zero non è mai una scelta valida.
Complessità attesa
tempo O(n * d), spazio aggiuntivo O(n)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.