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

Subtraia Dígitos para Chegar a Zero

Use o menor número possível de subtrações de dígitos para chegar a zero.

O que você vai aprender

  • Modelar um processo como estados e movimentos
  • Calcular os passos mínimos até zero
  • Comparar a DP com um atalho guloso

Problema

Ver original (inglês)

A cada passo, escolha um dígito decimal não nulo presente atualmente no número e subtraia esse dígito. Os dígitos são escolhidos a partir do novo valor após cada passo. Encontre o número mínimo de passos necessários para chegar a zero.

Implemente removing_digits(n).

Entrada

n: O número inicial positivo.

Saída

Retorne o menor número de passos de subtração.

Restrições

1 ≤ n ≤ 1.000.000. Subtrair zero não é uma jogada útil e está excluído.

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 usa três passos. Nenhuma das possíveis primeiras subtrações permite chegar a zero em apenas dois passos.

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

Subtraia o único dígito, 7, para chegar imediatamente a 0.

Como abordar

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

Dica 1

Cada número depende da melhor resposta para números menores alcançáveis ao subtrair um dígito.

Dica 2

Programação dinâmica para todos os valores até n evita trabalho repetido.

Dica 3

Lembre que os dígitos disponíveis mudam depois de cada subtração, e zero nunca é uma escolha válida.

Complexidade esperada

tempo O(n * d), espaço extra O(n)

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.