Todos los desafíos
Intermedio 1 resuelto 100.0% de aceptación

Subtract Digits to Reach Zero

Use as few digit subtractions as possible to reach zero.

Lo que aprenderás

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

Problema

Ver traducción

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.

Restricciones

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

Ejemplos

Ejemplo 1
Entrada:
n = 14

Salida esperada:
expected = 3
Entrada:
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 uses three steps. Neither possible first subtraction can reach zero in only two steps.

Ejemplo 2
Entrada:
n = 7

Salida esperada:
expected = 1
Entrada:
long long n = 7;

Salida esperada:
long long expected = 1;
Entrada:
long n = 7;

Salida esperada:
long expected = 1;

Explicación

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

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

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

Pista 2

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

Pista 3

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

Complejidad esperada

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

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 942 ms - 2/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 1 solución completa abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.