Happy Number

Q: Pourquoi le processus atteint-il toujours 1 ou une boucle ?

Un nombre à d chiffres est associé à une valeur d’au plus 81 × d , donc les grands nombres diminuent rapidement : tout nombre de départ inférieur ou égal à 2^31-1 passe sous 1000 après une étape, et un nombre inférieur à 1000 est associé à une valeur d’au plus 243. La suite est confinée à moins de 1000 valeurs, elle doit donc en revisiter une, puis elle entre dans un cycle. 1 est le seul nombre qui est associé à lui-même.

Q: Quelle est la complexité temporelle du nombre heureux ?

La première étape lit les chiffres O(log n) de n . Toutes les valeurs suivantes sont inférieures à 1000, et le parcours se répète en au plus 20 nombres ; le temps total est donc O(log n) . La version avec ensemble de hachage stocke les nombres visités ; la version de Floyd utilise un espace O(1) .

FacilePointeurs rapide et lent Hachage

+10

Partez d’un entier positif n et remplacez-le par la somme des carrés de ses chiffres, encore et encore. Par exemple, 12 devient 1² + 2² = 5. Si ce processus atteint 1, n est un nombre heureux ; sinon, il tourne indéfiniment en boucle parmi des nombres qui n’incluent jamais 1. Renvoyez true si n est heureux et false dans le cas contraire.

Fonction

isHappy(n: integer) → boolean

ninteger: l’entier positif à tester
Renvoieboolean: vrai si la répétition de la somme des carrés des chiffres atteint 1, faux si elle boucle indéfiniment

Contraintes

1 ≤ n ≤ 2³¹-1

Exemples

Entrée: n = 7
Sortie: true
Explication: 7 devient 49, puis 4² + 9² = 97, puis 130, puis 10, puis 1. Le processus atteint 1, donc 7 est heureux.

Entrée: n = 2
Sortie: false
Explication: 2 devient 4, 16, 37, 58, 89, 145, 42, 20 puis 4 à nouveau. À partir de là, les mêmes huit nombres se répètent indéfiniment et n’atteignent jamais 1.

Entrée: n = 100
Sortie: true
Explication: 1² + 0² + 0² = 1, donc 100 atteint 1 après une étape.

+16 tests cachés à la soumission

Pour aller plus loin

Comment compter rapidement les nombres heureux de 1 à 10^6, en réutilisant les résultats pour les nombres inférieurs à 1000 au lieu de reprendre chaque parcours depuis le début ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La suite ne peut jamais tendre vers l’infini. Un nombre à 10 chiffres correspond au plus à 10 × 81 = 810, et un nombre inférieur à 1000 correspond au plus à 3 × 81 = 243 ; après une étape, la suite reste donc parmi moins de 1000 valeurs et doit atteindre 1 ou répéter un nombre. Le problème devient alors une détection de cycle : mémorisez ce que vous avez vu, ou faites avancer un marcheur lent et un marcheur rapide et vérifiez s’ils se rencontrent.

Souviens-toi de chaque nombre que tu as vu

Intuition

Parcourez la suite et conservez chaque nombre dans un ensemble de hachage. Avant de passer à un nombre, vérifiez s’il se trouve déjà dans l’ensemble. Pour 2, l’ensemble se remplit avec 2, 4, 16, 37, 58, 89, 145, 42 et 20, et la valeur suivante est 4, qui s’y trouve déjà : le parcours a formé une boucle sans atteindre 1, donc 2 n’est pas heureux. Atteindre 1 met fin au parcours avec true.

C’est correct, car le nombre suivant dépend uniquement du nombre actuel. Lorsqu’un nombre réapparaît, tout ce qui suit se répète exactement ; aucun nouveau nombre ne peut donc apparaître, et 1 n’apparaîtra jamais.

Le parcours est court. La première étape lit les chiffres de n, soit O(log n), et chaque valeur ultérieure est inférieure à 1000, où aucun parcours ne visite plus de 20 nombres différents avant d’atteindre 1 ou de se répéter. L’ensemble contient ces nombres. Le code C utilise un tableau d’indicateurs de 1000 entrées comme ensemble et commence à enregistrer après la première étape, lorsque chaque valeur est inférieure à 1000.

Algorithme

Créez un ensemble de hachage vide seen.
Tant que n n’est pas égal à 1, renvoyez false si n se trouve dans seen.
Sinon, ajoutez n à seen et remplacez n par la somme des carrés de ses chiffres.
Lorsque la boucle se termine, n vaut 1 : renvoyez true.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    seen = set()
    while n != 1:
        if n in seen:
            return False  # back at an earlier number: a loop without 1
        seen.add(n)
        n = digitSquareSum(n)
    return True

Parcours rapides et lents (détection de cycle de Floyd)

Intuition

Considère chaque nombre comme un nœud avec une flèche pointant vers la somme des carrés de ses chiffres. En suivant les flèches à partir de n, on atteint soit 1, dont la flèche pointe vers 1, soit une boucle. C’est la forme d’une liste chaînée qui peut contenir un cycle, et l’algorithme de Floyd détecte un cycle sans rien stocker : slow avance d’un pas par tour et fast de deux.

Si la boucle ne contient pas 1, les deux marcheurs finissent par tourner en rond, et à chaque tour, fast gagne un pas sur slow : l’écart diminue donc d’une unité jusqu’à ce qu’ils se retrouvent sur le même nombre. Pour 2, ils se rencontrent à 42 après sept tours. Si le parcours atteint 1, fast y arrive en premier et y reste, car la somme pour 1 est 1. Arrête-toi donc lorsque fast vaut 1 ou que les marcheurs se rencontrent, puis vérifie si fast vaut 1.

Pour 7, slow passe par 7, 49, 97 tandis que fast passe par 49, 130, 1, et la boucle s’arrête avec fast sur 1. Le nombre de tours est au plus un petit multiple de la longueur du parcours : le temps d’exécution est donc comparable à celui de la version utilisant un ensemble, et la mémoire utilisée est de deux entiers.

Algorithme

Écrivez une fonction auxiliaire qui renvoie la somme des carrés des chiffres d’un nombre.
Définissez slow = n et définissez fast comme le nombre situé un pas après n.
Tant que fast n’est pas égal à 1 et que slow est différent de fast, faites avancer slow d’un pas et fast de deux pas.
Renvoie si fast est égal à 1.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    slow = n
    fast = digitSquareSum(n)
    # fast moves two steps for every step of slow; they meet only inside a loop.
    while fast != 1 and slow != fast:
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    return fast == 1

Pièges et cas limites

Le calcul des chiffres est simple. La plupart des erreurs concernent le moment où la boucle s’arrête.

Faire une boucle jusqu’à ce que la valeur soit 1, sans autre condition de sortie. Pour 2, cette boucle ne se termine jamais.
Initialiser slow et fast avec le même nombre et tester slow != fast avant le premier déplacement. La boucle ne s’exécute jamais, et 7 est considéré comme malheureux. Initialisez fast avec un coup d’avance, ou déplacez les deux avant la première comparaison.
Renvoyer slow == 1 dans la version de Floyd. fast atteint 1 en premier et la boucle s’arrête immédiatement, alors que slow peut encore être à 97.
Sommer les chiffres au lieu de leurs carrés, ou élever au carré le nombre entier. Pour 12, la valeur suivante est 1² + 2² = 5, et non 3 ni 144.
Déclarer n malheureux dès que les pointeurs se rencontrent. 1 se transforme en lui-même, donc les pointeurs se rencontrent aussi sur 1 ; vérifiez où ils se sont rencontrés, ou arrêtez-vous dès que fast vaut 1.

Questions fréquentes4

Pourquoi le processus atteint-il toujours 1 ou une boucle ?

Un nombre à d chiffres est associé à une valeur d’au plus 81 × d, donc les grands nombres diminuent rapidement : tout nombre de départ inférieur ou égal à 2^31-1 passe sous 1000 après une étape, et un nombre inférieur à 1000 est associé à une valeur d’au plus 243. La suite est confinée à moins de 1000 valeurs, elle doit donc en revisiter une, puis elle entre dans un cycle. 1 est le seul nombre qui est associé à lui-même.

Quelle est la complexité temporelle du nombre heureux ?

La première étape lit les chiffres O(log n) de n. Toutes les valeurs suivantes sont inférieures à 1000, et le parcours se répète en au plus 20 nombres ; le temps total est donc O(log n). La version avec ensemble de hachage stocke les nombres visités ; la version de Floyd utilise un espace O(1).

Pourquoi tous les nombres malheureux finissent-ils par aboutir à 4 ?

Vérifier chaque nombre inférieur à 1000 montre qu'il existe exactement une boucle qui n'atteint pas 1 : 4, 16, 37, 58, 89, 145, 42, 20, puis retour à 4. Comme chaque valeur de départ descend en dessous de 1000, tout nombre malheureux finit par tomber dans cette boucle. Une solution peut s'arrêter dès qu'elle atteint 4, mais cela repose sur un fait qu'il faudrait justifier lors d'un entretien ; l'ensemble et la méthode de Floyd ne nécessitent pas de connaître ce fait.

Quel est le lien entre le nombre heureux et le cycle dans une liste chaînée ?

Les deux posent la question de savoir si, en suivant une flèche à partir de chaque élément, on revient un jour à un élément déjà visité. Dans Happy Number, la flèche correspond à la somme des carrés des chiffres ; dans une liste chaînée, elle correspond au pointeur suivant. C’est pourquoi les parcours rapide et lent de Floyd permettent de résoudre les deux problèmes avec une mémoire constante.

Python

def isHappy(n):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

n = 7

Attendu

true