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

Nombre heureux

Déterminez si, en additionnant les carrés des chiffres d'un nombre encore et encore, on finit par obtenir 1.

Ce que vous allez apprendre

  • Calculer la somme des carrés des chiffres
  • Détecter une suite qui se répète avec un ensemble ou deux pointeurs
  • Arrêter une boucle sur l'une ou l'autre de deux conditions

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

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

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

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.