Problema
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
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.
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.