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

Restar Dígitos para Llegar a Cero

Usa la menor cantidad posible de restas de dígitos para llegar a cero.

Lo que aprenderás

  • Modelar un proceso como estados y movimientos
  • Calcular los pasos mínimos hasta cero
  • Comparar la DP con un atajo voraz

Problema

Ver original (inglés)

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

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 usa tres pasos. Ninguna de las posibles primeras restas puede llegar a cero en solo dos pasos.

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

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.

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.