Problema
En cada paso, elige un dígito decimal distinto de cero que esté presente actualmente en el número y réstalo. Los dígitos se toman del nuevo valor después de cada paso. Encuentra el número mínimo de pasos necesarios para llegar a cero.
Implementa removing_digits(n).
Entrada
n: El número inicial positivo.
Salida
Devuelve la menor cantidad de pasos de resta.
Restricciones
1 ≤ n ≤ 1,000,000. Restar cero no es un movimiento útil y está excluido.
Ejemplos
Entrada:
n = 14
Salida esperada:
expected = 3Entrada:
long long n = 14;
Salida esperada:
long long expected = 3;Entrada:
long n = 14;
Salida esperada:
long expected = 3;Explicación
14 → 10 → 9 → 0 usa tres pasos. Ninguna de las posibles primeras restas puede llegar a cero en solo dos pasos.
Entrada:
n = 7
Salida esperada:
expected = 1Entrada:
long long n = 7;
Salida esperada:
long long expected = 1;Entrada:
long n = 7;
Salida esperada:
long expected = 1;Explicación
Resta el único dígito, 7, para llegar a 0 inmediatamente.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Cada número depende de la mejor respuesta para números menores a los que puedes llegar restando un dígito.
Pista 2
La programación dinámica sobre todos los valores hasta n evita recalcular trabajo.
Pista 3
Recuerda que los dígitos disponibles cambian tras cada resta, y cero nunca es una opción válida.
Complejidad esperada
tiempo O(n * d), espacio extra O(n)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.