Todos os desafios
Difícil 0 resolvidos 0% de aceitação

Cadeias de fatoriais dos dígitos

Conte os números iniciais cuja cadeia de fatoriais dos dígitos tem exatamente uma dada quantidade de termos distintos.

O que você vai aprender

  • Seguir uma cadeia até um valor se repetir
  • Encontrar o comprimento das cadeias dentro e antes de um ciclo
  • Reaproveitar comprimentos já guardados

Problema

Ver original (inglês)

Substitua um número pela soma dos fatoriais dos seus dígitos: 145 dá 1! + 4! + 5! = 145 de novo, e 69 dá 6! + 9! = 363600. Repetindo isso, sempre se cai em um ciclo. A cadeia de um número inicial são os seus termos até a primeira repetição: 69, 363600, 1454, 169, 363601 e então 1454 de novo, então o 69 tem 5 termos distintos. Conte os números iniciais de 1 a limit cuja cadeia tem exatamente length termos distintos.

Implemente digit_factorial_chains(limit, length).

Muitas cadeias passam pelos mesmos números. Guarde o comprimento da cadeia de cada número assim que ele for conhecido e reaproveite-o.

Entrada

limit: o maior número inicial.

length: a quantidade de termos distintos desejada, incluindo o número inicial.

Saída

Retorne quantos números iniciais n com 1 ≤ n ≤ limit têm exatamente length termos distintos na sua cadeia.

Restrições

1 ≤ limit ≤ 100 000; 1 ≤ length ≤ 70

Exemplos

Exemplo 1
Entrada:
limit = 2
length = 1

Saída esperada:
expected = 2
Entrada:
long long limit = 2;
long long length = 1;

Saída esperada:
long long expected = 2;
Entrada:
long limit = 2;
long length = 1;

Saída esperada:
long expected = 2;

Explicação

1! = 1 e 2! = 2, então 1 e 2 levam a si mesmos e têm cadeias de 1 termo. A resposta é 2.

Exemplo 2
Entrada:
limit = 10
length = 2

Saída esperada:
expected = 1
Entrada:
long long limit = 10;
long long length = 2;

Saída esperada:
long long expected = 1;
Entrada:
long limit = 10;
long length = 2;

Saída esperada:
long expected = 1;

Explicação

3 dá 6, depois 720, 5043, ..., então a cadeia é longa. 10 dá 1! + 0! = 2 e depois 2 de novo: dois termos. Só o 10 tem exatamente 2, então a resposta é 1.

Como abordar

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

Dica 1

Calcule de 0! a 9! uma única vez, antes de tudo.

Dica 2

Registre o número do passo de cada valor na cadeia atual; uma repetição mostra onde o ciclo começa.

Dica 3

Todos os valores dentro do ciclo têm o comprimento do ciclo, e cada valor antes dele tem um a mais que o seguinte.

Complexidade esperada

tempo O(limit × log limit) com memoização, espaço extra O(limit)

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.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.