Problème
Partez d'un entier strictement positif et remplacez-le par la somme des carrés de ses chiffres. Recommencez. Si l'on finit par tomber sur 1, le nombre de départ est heureux. Sinon, le processus entre dans un cycle qui ne contient jamais 1, et le nombre est malheureux. Par exemple, 7 → 49 → 97 → 130 → 10 → 1, donc 7 est heureux.
Implémentez happy_number(n).
Il vous faut un moyen de repérer que la suite commence à se répéter, afin que la boucle s'arrête aussi pour les nombres malheureux.
Entrée
n : le nombre de départ.
Sortie
Renvoyez true si le processus atteint 1, sinon false. Le nombre 1 lui-même est heureux.
Contraintes
1 ≤ n ≤ 10^9
Exemples
Entrée :
n = 19
Sortie attendue :
expected = True
Entrée :
long long n = 19;
Sortie attendue :
bool expected = true;
Entrée :
long n = 19;
Sortie attendue :
bool expected = true;
Explication
1² + 9² = 82, puis 8² + 2² = 68, puis 6² + 8² = 100, puis 1² + 0² + 0² = 1, donc 19 est heureux : true.
Entrée :
n = 4
Sortie attendue :
expected = False
Entrée :
long long n = 4;
Sortie attendue :
bool expected = false;
Entrée :
long n = 4;
Sortie attendue :
bool expected = false;
Explication
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 se répète sans jamais atteindre 1, donc la réponse est false.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Écrivez une fonction auxiliaire qui associe à un nombre la somme des carrés de ses chiffres.
Indice 2
Un nombre malheureux finit par redonner une valeur déjà obtenue, mémorisez donc les valeurs rencontrées.
Indice 3
La suite descend très vite sous quelques centaines, l'ensemble reste donc petit.
Complexité attendue
O(log n) étapes par nombre, espace supplémentaire O(1) avec deux pointeurs
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.