Problème
Remplacez un nombre par la somme des factorielles de ses chiffres : 145 donne 1! + 4! + 5! = 145, c'est-à-dire lui-même, et 69 donne 6! + 9! = 363600. En répétant l'opération, on finit toujours dans une boucle. La chaîne d'un nombre de départ est la liste de ses termes jusqu'à la première répétition : 69, 363600, 1454, 169, 363601, puis de nouveau 1454 ; 69 a donc 5 termes distincts. Comptez les nombres de départ de 1 à limit dont la chaîne contient exactement length termes distincts.
Implémentez digit_factorial_chains(limit, length).
Beaucoup de chaînes passent par les mêmes nombres. Mémorisez la longueur de chaîne de chaque nombre dès qu'elle est connue et réutilisez-la.
Entrée
limit : le plus grand nombre de départ.
length : le nombre de termes distincts voulu, départ compris.
Sortie
Renvoyez combien de nombres de départ n, avec 1 ≤ n ≤ limit, ont exactement length termes distincts dans leur chaîne.
Contraintes
1 ≤ limit ≤ 100 000 ; 1 ≤ length ≤ 70
Exemples
Entrée :
limit = 2
length = 1
Sortie attendue :
expected = 2
Entrée :
long long limit = 2;
long long length = 1;
Sortie attendue :
long long expected = 2;
Entrée :
long limit = 2;
long length = 1;
Sortie attendue :
long expected = 2;
Explication
1! = 1 et 2! = 2, donc 1 et 2 sont chacun envoyés sur eux-mêmes et ont une chaîne d'un seul terme. La réponse est 2.
Entrée :
limit = 10
length = 2
Sortie attendue :
expected = 1
Entrée :
long long limit = 10;
long long length = 2;
Sortie attendue :
long long expected = 1;
Entrée :
long limit = 10;
long length = 2;
Sortie attendue :
long expected = 1;
Explication
3 donne 6, puis 720, 5043, ... : sa chaîne est longue. 10 donne 1! + 0! = 2, puis encore 2, soit deux termes. Seul 10 en a exactement 2, donc la réponse est 1.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Précalculez une fois pour toutes 0! à 9!.
Indice 2
Notez le numéro d'étape de chaque valeur dans la chaîne courante ; une répétition vous indique où commence la boucle.
Indice 3
Les valeurs de la boucle ont toutes la longueur de la boucle, et chaque valeur située avant a une unité de plus que la suivante.
Complexité attendue
temps O(limit × log limit) avec mémoïsation, espace supplémentaire O(limit)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.