Problème
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
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 uses three steps. Neither possible first subtraction can reach zero in only two steps.
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
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.