Problème
À chaque étape, choisissez un chiffre décimal non nul actuellement présent dans le nombre et soustrayez ce chiffre. Les chiffres sont pris à partir de la nouvelle valeur après chaque étape. Trouvez le nombre minimal d'étapes nécessaires pour atteindre zéro.
Implémentez removing_digits(n).
Entrée
n : Le nombre de départ, strictement positif.
Sortie
Retournez le nombre minimal d'étapes de soustraction.
Contraintes
1 ≤ n ≤ 1 000 000. Soustraire zéro n'est pas un coup utile et est exclu.
Exemples
Entrée :
n = 14
Sortie attendue :
expected = 3Entrée :
long long n = 14;
Sortie attendue :
long long expected = 3;Entrée :
long n = 14;
Sortie attendue :
long expected = 3;Explication
14 → 10 → 9 → 0 utilise trois étapes. Aucune des deux soustractions initiales possibles ne permet d'atteindre zéro en seulement deux étapes.
Entrée :
n = 7
Sortie attendue :
expected = 1Entrée :
long long n = 7;
Sortie attendue :
long long expected = 1;Entrée :
long n = 7;
Sortie attendue :
long expected = 1;Explication
Soustrayez le seul chiffre, 7, pour atteindre directement 0.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Chaque nombre dépend de la meilleure réponse pour des nombres plus petits atteignables en soustrayant un chiffre.
Indice 2
Une programmation dynamique sur toutes les valeurs jusqu’à n évite de refaire le travail.
Indice 3
Souviens-toi que les chiffres disponibles changent après chaque soustraction, et que zéro n’est jamais un choix valide.
Complexité attendue
temps O(n * d), espace supplémentaire O(n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.