Problema
Sustituye un número por la suma de los factoriales de sus cifras: 145 da 1! + 4! + 5! = 145 otra vez, y 69 da 6! + 9! = 363600. Si repites el proceso, siempre acabas cayendo en un ciclo. La cadena de un número inicial está formada por sus términos hasta la primera repetición: 69, 363600, 1454, 169, 363601 y luego otra vez 1454, así que 69 tiene 5 términos distintos. Cuenta los números iniciales del 1 a limit cuya cadena tiene exactamente length términos distintos.
Implementa digit_factorial_chains(limit, length).
Muchas cadenas pasan por los mismos números. Guarda la longitud de la cadena de cada número en cuanto la conozcas y reutilízala.
Entrada
limit: el mayor número inicial.
length: la cantidad de términos distintos buscada, incluido el inicial.
Salida
Devuelve cuántos números iniciales n con 1 ≤ n ≤ limit tienen exactamente length términos distintos en su cadena.
Restricciones
1 ≤ limit ≤ 100,000; 1 ≤ length ≤ 70
Ejemplos
Entrada:
limit = 2
length = 1
Salida esperada:
expected = 2
Entrada:
long long limit = 2;
long long length = 1;
Salida esperada:
long long expected = 2;
Entrada:
long limit = 2;
long length = 1;
Salida esperada:
long expected = 2;
Explicación
1! = 1 y 2! = 2, así que el 1 y el 2 se transforman en sí mismos y su cadena tiene 1 término. La respuesta es 2.
Entrada:
limit = 10
length = 2
Salida esperada:
expected = 1
Entrada:
long long limit = 10;
long long length = 2;
Salida esperada:
long long expected = 1;
Entrada:
long limit = 10;
long length = 2;
Salida esperada:
long expected = 1;
Explicación
3 da 6, luego 720, 5043, ... así que su cadena es larga. 10 da 1! + 0! = 2 y luego otra vez 2: dos términos. Solo el 10 tiene exactamente 2, así que la respuesta es 1.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Calcula de antemano, una sola vez, los valores de 0! a 9!.
Pista 2
Anota en qué paso de la cadena actual aparece cada valor; una repetición te dice dónde empieza el ciclo.
Pista 3
Todos los valores del ciclo tienen la longitud del ciclo, y cada valor anterior a él tiene uno más que el siguiente.
Complejidad esperada
tiempo O(limit × log limit) con memoización, espacio extra O(limit)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.