Todos los desafíos
Difícil 0 resueltos 0% de aceptación

Cadenas de factoriales de cifras

Cuenta los números iniciales cuya cadena de factoriales de cifras tiene exactamente una cantidad dada de términos distintos.

Lo que aprenderás

  • Seguir una cadena hasta que un valor se repita
  • Calcular las longitudes dentro del ciclo y antes de él
  • Reutilizar las longitudes guardadas

Problema

Ver original (inglés)

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

Ejemplo 1
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.

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

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.