Tous les défis
Moyen 1 résolu 100.0 % de réussite

Subtract Digits to Reach Zero

Use as few digit subtractions as possible to reach zero.

Ce que vous allez apprendre

  • Model a process as states and moves
  • Compute the minimum steps to zero
  • Compare DP with a greedy shortcut

Problème

Afficher la traduction

At each step, choose a nonzero decimal digit currently present in the number and subtract that digit. Digits are taken from the new value after every step. Find the minimum number of steps needed to reach zero.

Implement removing_digits(n).

Input

n: The positive starting number.

Output

Return the fewest subtraction steps.

Contraintes

1 ≤ n ≤ 1,000,000. Subtracting zero is not a useful move and is excluded.

Exemples

Exemple 1
Entrée :
n = 14

Sortie attendue :
expected = 3
Entré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 uses three steps. Neither possible first subtraction can reach zero in only two steps.

Exemple 2
Entrée :
n = 7

Sortie attendue :
expected = 1
Entrée :
long long n = 7;

Sortie attendue :
long long expected = 1;
Entrée :
long n = 7;

Sortie attendue :
long expected = 1;

Explication

Subtract the only digit, 7, to reach 0 immediately.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Each number depends on the best answer for smaller numbers reachable by subtracting one digit.

Indice 2

Dynamic programming over all values up to n avoids repeated work.

Indice 3

Remember that the available digits change after every subtraction, and zero is never a valid choice.

Complexité attendue

O(n * d) time, O(n) extra space

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 942 ms - 2/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.