Problème
Partant d'un entier positif n, la règle de Collatz (suite de Syracuse) donne comme terme suivant n / 2 si n est pair et 3n + 1 si n est impair, et la suite s'arrête lorsqu'elle atteint 1. Pour 6, on obtient 6, 3, 10, 5, 16, 8, 4, 2, 1, soit neuf termes. Parmi tous les nombres de départ de 1 à limit, trouvez celui qui produit le plus de termes.
Implémentez longest_collatz_chain(limit).
Les suites ont des fins communes : mémoriser la longueur trouvée pour chaque nombre évite beaucoup de calculs. En chemin, les termes peuvent dépasser la limite ; utilisez des entiers sur 64 bits.
Entrée
limit : le plus grand nombre de départ à essayer.
Sortie
Renvoyez le nombre de départ dont la suite a le plus de termes (en comptant le départ et le 1 final). En cas d'égalité, renvoyez le plus petit.
Contraintes
1 ≤ limit ≤ 100 000
Exemples
Entrée :
limit = 6
Sortie attendue :
expected = 6
Entrée :
long long limit = 6;
Sortie attendue :
long long expected = 6;
Entrée :
long limit = 6;
Sortie attendue :
long expected = 6;
Explication
Pour les départs de 1 à 6, les suites ont 1, 2, 8, 3, 6 et 9 termes, donc la réponse est 6.
Entrée :
limit = 10
Sortie attendue :
expected = 9
Entrée :
long long limit = 10;
Sortie attendue :
long long expected = 9;
Entrée :
long limit = 10;
Sortie attendue :
long expected = 9;
Explication
9 donne 20 termes (9, 28, 14, 7, ...), plus que tout autre départ jusqu'à 10, donc la réponse est 9.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Commencez par compter les termes d'une seule suite, départ et 1 compris.
Indice 2
Quand une suite atteint un nombre dont vous connaissez déjà la longueur, additionnez au lieu de continuer.
Indice 3
Ne remplacez le meilleur départ que si la longueur est strictement plus grande.
Complexité attendue
temps O(limit × average new steps), c'est-à-dire limit fois le nombre moyen de nouvelles étapes, espace supplémentaire O(limit)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.