Tous les défis
Difficile 0 résolus 0 % de réussite

Chaînes de factorielles des chiffres

Compter les nombres de départ dont la chaîne de factorielles des chiffres contient exactement un nombre donné de termes distincts.

Ce que vous allez apprendre

  • Suivre une chaîne jusqu'à ce qu'une valeur se répète
  • Trouver la longueur des chaînes dans une boucle et avant celle-ci
  • Réutiliser les longueurs mémorisées

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

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

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.