Todos os desafios
Médio 1 resolvido 100.0% de aceitação

Subtract Digits to Reach Zero

Use as few digit subtractions as possible to reach zero.

O que você vai aprender

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

Problema

Ver tradução

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.

Restrições

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

Exemplos

Exemplo 1
Entrada:
n = 14

Saída esperada:
expected = 3
Entrada:
long long n = 14;

Saída esperada:
long long expected = 3;
Entrada:
long n = 14;

Saída esperada:
long expected = 3;

Explicação

14 → 10 → 9 → 0 uses three steps. Neither possible first subtraction can reach zero in only two steps.

Exemplo 2
Entrada:
n = 7

Saída esperada:
expected = 1
Entrada:
long long n = 7;

Saída esperada:
long long expected = 1;
Entrada:
long n = 7;

Saída esperada:
long expected = 1;

Explicação

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

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

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

Dica 2

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

Dica 3

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

Complexidade esperada

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

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

# Programador Linguagem Tempo Memória Avaliação da IA Solução
1 ННикита Python 942 ms - 2/5 Ver código

Aprenda com outros

Soluções da comunidade

Atenção: 1 solução completa abaixo Tente resolver sozinho primeiro. Você ainda pode espiar o código de outros desenvolvedores e as avaliações da IA. Entre e resolva o desafio para participar da discussão.