Armstrong Number

Q: Quelle est la complexité temporelle de la vérification d’un nombre d’Armstrong ?

n a environ log n chiffres, au maximum 10 ici. Extraire les chiffres et rechercher chaque puissance dans une table de dix éléments prend un temps de O(log n) et un espace de O(1) . Recalculer d^k avec une boucle pour chaque chiffre donne une complexité de O(log² n) , ce qui reste rapide à cette taille.

DébutantMaths et simulation

+10

Un entier positif est un nombre d’Armstrong lorsqu’il est égal à la somme de ses chiffres, chacun élevé à la puissance correspondant au nombre de chiffres qu’il comporte. 153 comporte trois chiffres et 1^3 + 5^3 + 3^3 = 153, c’est donc un nombre d’Armstrong. Écris une fonction qui reçoit n et renvoie true s’il s’agit d’un nombre d’Armstrong, et false dans le cas contraire.

Fonction

isArmstrong(n: integer) → boolean

ninteger: l’entier positif à tester
Renvoieboolean: vrai lorsque n est égal à la somme de ses chiffres, chacun élevé à la puissance du nombre de chiffres

Contraintes

1 ≤ n ≤ 10⁹

Exemples

Entrée: n = 153
Sortie: true
Explication: 153 a 3 chiffres, donc chaque chiffre est élevé au cube : 1 + 125 + 27 = 153. La somme redonne le nombre, donc la réponse est true.

Entrée: n = 10
Sortie: false
Explication: 10 a 2 chiffres, donc chaque chiffre est élevé au carré : 1 + 0 = 1, ce qui n'est pas 10. La réponse est false.

Entrée: n = 9474
Sortie: true
Explication: Avec 4 chiffres, la puissance est 4 : 6561 + 256 + 2401 + 256 = 9474, le nombre lui-même, donc la réponse est true.

+31 tests cachés à la soumission

Pour aller plus loin

Seuls 31 nombres d’Armstrong se trouvent entre 1 et 10^9. Peux-tu tous les lister sans tester un milliard de nombres un par un ?

Indices

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

0 sur 3 ouverts

Solution

La définition est l’algorithme : trouver le nombre de chiffres de n, élever chaque chiffre à cette puissance, additionner les résultats et comparer avec n. Les pièges se trouvent dans les nombres. L’exposant est le nombre de chiffres de ce n particulier, et non un 3 fixe, et la somme peut dépasser un entier de 32 bits : pour 999999999, elle vaut 9 × 9^9 = 3486784401.

Lire les chiffres de la chaîne

Intuition

La représentation décimale de n te donne les deux éléments dont tu as besoin. Sa longueur est l’exposant k, et ses caractères sont les chiffres. Pour 9474, la chaîne comporte 4 caractères, donc tu additionnes 9^4 + 4^4 + 7^4 + 4^4.

Convertis chaque caractère en son chiffre, élève-le à la puissance k, puis ajoute-le à un total cumulé. n est un nombre d’Armstrong si et seulement si le total final est égal à n.

Conserve le total dans un entier de 64 bits. n tient sur 32 bits, mais la somme n’y tient pas nécessairement : 999999999 donne 3486784401, qui dépasse la limite de 32 bits, 2147483647. Calculer une puissance avec une boucle de k multiplications coûte k étapes par chiffre, donc le test est en O(k²), avec k d’environ log n. Ici, cela représente au plus 100 multiplications, et la chaîne utilise k caractères de mémoire.

Algorithme

Convertis n en sa représentation décimale sous forme de chaîne et note k sa longueur.
Définis un total de 64 bits à 0.
Pour chaque caractère, convertis-le en chiffre d et ajoute d^k à total, en multipliant des nombres entiers plutôt qu'en appelant une fonction de puissance à virgule flottante.
Retourne si total est égal à n.

def isArmstrong(n):
    digits = str(n)
    k = len(digits)
    total = 0
    for ch in digits:
        total += int(ch) ** k
    return total == n

Extrais les chiffres et consulte leurs puissances

Intuition

L’arithmétique seule fait le même travail sans chaîne de caractères. m % 10 est le dernier chiffre de m et la division entière par 10 le supprime : une boucle qui divise par 10 jusqu’à ce qu’il ne reste plus rien compte les chiffres. 9474 devient 947, 94, 9, 0 : quatre étapes, donc k = 4.

Il n’existe que dix chiffres, alors construis une table powers[d] = d^k pour d de 0 à 9 avant d’additionner quoi que ce soit. Chaque chiffre nécessite alors une seule consultation au lieu de k multiplications. La vérification passe à un temps de O(log n), et la table a une taille fixe de dix éléments, soit un espace de O(1).

La deuxième boucle extrait à nouveau les chiffres et ajoute powers[m % 10] au total. Chaque terme est nul ou positif, donc le total ne diminue jamais, et dès qu’il dépasse n, la réponse est false. Pour 999999999, cela se produit après trois chiffres, à 3 × 387420489 = 1162261467. La table nécessite tout de même 64 bits, car n = 10^9 a dix chiffres et 9^10 = 3486784401.

Algorithme

Comptez les chiffres de n en divisant une copie par 10 jusqu’à ce qu’elle atteigne 0 ; appelez ce nombre k.
Remplissez powers[d] = d^k pour chaque chiffre d de 0 à 9, dans des entiers 64 bits.
Divisez à nouveau une copie fraîche de n par 10, en ajoutant powers[m % 10] à total à chaque étape.
Si total dépasse n, renvoyez immédiatement false.
Après le dernier chiffre, renvoyez si total est égal à n.

def isArmstrong(n):
    # Count the digits: k is the exponent.
    k = 0
    m = n
    while m > 0:
        k += 1
        m //= 10
    # powers[d] = d^k for the ten possible digits.
    powers = [d ** k for d in range(10)]
    total = 0
    m = n
    while m > 0:
        total += powers[m % 10]
        if total > n:
            return False  # the total only grows
        m //= 10
    return total == n

Pièges et cas limites

La formule est courte, donc les bogues viennent des nombres qui l’entourent.

Un exposant fixe de 3. Cela accepte 153 et 370, mais rejette 9474, et rejette tous les nombres à un chiffre supérieurs à 1, puisque 7^3 = 343.
Une somme sur 32 bits. 999999999 donne la somme 3486784401, et l’entrée de la table 9^10 est le même nombre. En C, ce dépassement de capacité entraîne un comportement indéfini ; Java et C# reviennent à un nombre négatif, et une compilation Rust en mode débogage déclenche une panique. Utilisez long, long long ou i64.
Les puissances en virgule flottante. pow en C et Math.pow en Java renvoient un double. Certains environnements d’exécution C ont renvoyé une valeur légèrement inférieure à un nombre entier, comme 24.999... pour 5^2, qu’une conversion tronque à 24. Multipliez plutôt des nombres entiers dans une boucle.
Comparer avec la mauvaise valeur. Les boucles sur les chiffres divisent n jusqu’à 0 ; travaillez donc sur une copie et comparez le total à la valeur d’origine.
La notation scientifique. En R, as.character(1e9) est "1e+09", soit cinq caractères ; une solution en R basée sur les chaînes formate donc avec sprintf("%.0f", n).

Questions fréquentes4

Qu’est-ce qu’un nombre d’Armstrong ?

Un nombre d’Armstrong, également appelé nombre narcissique, est égal à la somme de ses propres chiffres, chacun élevé à la puissance du nombre de chiffres. 153 en est un, car 1^3 + 5^3 + 3^3 = 153, et 9474 en est un, car 9^4 + 4^4 + 7^4 + 4^4 = 9474. Tout nombre à un chiffre convient, puisque d^1 = d.

Combien y a-t-il de nombres d’Armstrong ?

En base 10, il existe exactement 88 nombres positifs égaux à la somme des puissances de leurs chiffres, et le plus grand a 39 chiffres. La liste est finie, car un nombre de k chiffres est au moins égal à 10^(k-1), tandis que la somme des puissances de ses chiffres est au plus égale à k × 9^k, et à partir de 61 chiffres, la somme ne peut jamais rattraper son retard. Entre 1 et 10^9, il y en a 31.

Pourquoi la vérification d’un nombre d’Armstrong nécessite-t-elle un entier de 64 bits ?

La valeur d’entrée tient sur 32 bits, mais la somme des chiffres élevés à une puissance peut être plusieurs fois supérieure au nombre. 999999999 donne 9 × 9^9 = 3486784401, ce qui dépasse 2^31-1 = 2147483647. Un total sur 32 bits déborde dans ce cas ; stocke donc le total et les puissances dans un type sur 64 bits.

Quelle est la complexité temporelle de la vérification d’un nombre d’Armstrong ?

n a environ log n chiffres, au maximum 10 ici. Extraire les chiffres et rechercher chaque puissance dans une table de dix éléments prend un temps de O(log n) et un espace de O(1). Recalculer d^k avec une boucle pour chaque chiffre donne une complexité de O(log² n), ce qui reste rapide à cette taille.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

n = 153

Attendu

true