Sum of Digits

Q: Quelle est la complexité temporelle de la somme des chiffres d’un nombre ?

Une étape par chiffre, donc O(d) , où d est le nombre de chiffres. Un nombre n comporte environ log10(n) + 1 chiffres, donc la même borne s’écrit souvent O(log n) . Pour un entier de 32 bits, cela représente au maximum 10 étapes.

Q: Comment obtenir les chiffres d’un nombre sans le convertir en chaîne de caractères ?

Utilisez le reste et la division entière par 10. n % 10 est le dernier chiffre, et diviser n par 10 en supprimant le reste élimine ce chiffre. Répétez jusqu’à ce que n atteigne 0, et vous parcourrez chaque chiffre de droite à gauche.

Q: La version chaîne de caractères ou la version arithmétique est-elle meilleure ?

Les deux sont en O(d) et les deux sont correctes. La version avec une chaîne de caractères est plus courte à écrire dans de nombreux langages, mais crée une copie des chiffres. La version arithmétique utilise O(1) de mémoire supplémentaire et montre à l’intervieweur que tu sais comment % 10 et / 10 décomposent un nombre, ce qui est utile dans les problèmes de palindrome et d’inversion des chiffres.

DébutantMaths et simulation

+10

On vous donne un entier non négatif n. Retournez la somme de ses chiffres décimaux. Par exemple, les chiffres de 482 sont 4, 8 et 2, donc la réponse est 14.

Fonction

sumOfDigits(n: integer) → integer

ninteger: l’entier non négatif dont tu additionnes les chiffres
Renvoieinteger: la somme des chiffres décimaux de n

Contraintes

0 ≤ n ≤ 2³¹-1

Exemples

Entrée: n = 9045
Sortie: 18
Explication: Les chiffres de 9045 sont 9, 0, 4 et 5, et 9 + 0 + 4 + 5 = 18. Le zéro n’ajoute rien, mais compte tout de même comme un chiffre.

Entrée: n = 7
Sortie: 7
Explication: Un nombre à un chiffre est égal à la somme de ses chiffres, donc 7 donne 7.

+15 tests cachés à la soumission

Indices

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

0 sur 3 ouverts

Solution

Un nombre ne vous donne pas ses chiffres un par un ; vous devez le décomposer. Vous pouvez le convertir en texte et lire les caractères, ou utiliser les deux opérations arithmétiques qui retirent le dernier chiffre : n % 10 le donne, et la division entière par 10 le retire. Les deux nécessitent une étape par chiffre, notée d ci-dessous, et d ≤ 10 ici. La version arithmétique ne nécessite pas de mémoire supplémentaire.

Lisez les chiffres comme du texte

Intuition

Quand tu écris un nombre, tu en vois déjà les chiffres. Convertis n en texte décimal : 9045 devient les quatre caractères 9, 0, 4 et 5, puis parcours les caractères et additionne la valeur de chacun.

Un caractère n’est pas encore un nombre. Le caractère '4' est stocké sous forme du code 52 ; tu dois donc l’analyser ou soustraire le code de '0' : '4' - '0' = 4. Les caractères correspondant aux chiffres ont des codes consécutifs, ce qui explique pourquoi cette soustraction fonctionne pour les dix chiffres.

Le texte comporte d caractères, un par chiffre ; la boucle prend donc un temps de O(d), et le texte lui-même occupe un espace supplémentaire de O(d).

Algorithme

Convertis n en texte décimal.
Définis total = 0.
Pour chaque caractère, ajoute sa valeur numérique à total.
Retourne total.

def sumOfDigits(n):
    total = 0
    for digit in str(n):
        total += int(digit)
    return total

Retire le dernier chiffre avec % 10

Intuition

Vous pouvez décomposer un nombre sans aucun texte. Le reste d’une division par 10 est le dernier chiffre : 9045 % 10 = 5. La division entière par 10 élimine ce chiffre : 9045 / 10 = 904 lorsque la partie fractionnaire est supprimée. Répétez cette paire d’opérations et les chiffres apparaissent de droite à gauche.

Pour 9045 : ajoutez 5 et gardez 904, ajoutez 4 et gardez 90, ajoutez 0 et gardez 9, ajoutez 9 et gardez 0. La boucle s’arrête à 0 avec un total de 18. Pour n = 0, la boucle ne s’exécute jamais et la réponse est 0, ce qui est correct.

Chaque étape supprime un chiffre, il y a donc d étapes, un temps d’exécution de O(d) et seulement deux entiers en mémoire, soit un espace de O(1). Chaque valeur intermédiaire est inférieure à n, donc rien ne peut déborder.

Algorithme

Définissez total = 0.
Tant que n > 0, ajoutez n % 10 à total.
Divisez n par 10 en supprimant la partie fractionnaire.
Lorsque n atteint 0, renvoyez total.

def sumOfDigits(n):
    total = 0
    while n > 0:
        total += n % 10  # last digit
        n //= 10         # drop the last digit
    return total

Pièges et cas limites

La boucle est courte, et les erreurs portent sur les types et la plus petite entrée.

Utiliser / alors que le langage effectue une division réelle. En JavaScript, TypeScript, Lua, PHP et R, 9045 / 10 vaut 904.5, et la boucle additionne alors des fractions. Arrondissez à l’entier inférieur avec Math.floor ou math.floor ; en Python, utilisez //, en Dart ~/, en PHP intdiv, en R %/%.
Ajouter des caractères au lieu de chiffres. Le caractère '7' a pour code 55, et non 7. Soustrayez '0' ou analysez d’abord le caractère.
Effectuer une boucle tant que n >= 10. La boucle s’arrête alors avec le chiffre initial encore dans n et ne l’ajoute jamais, donc 9045 donne 9 au lieu de 18. Effectuez la boucle tant que n > 0, ce qui renvoie également 0 lorsque n = 0.
Afficher de grands nombres sous forme de texte en R. as.character(100000) donne "1e+05", et non les six chiffres du nombre. Utilisez format(n, scientific = FALSE).

Questions fréquentes4

Quelle est la complexité temporelle de la somme des chiffres d’un nombre ?

Une étape par chiffre, donc O(d), où d est le nombre de chiffres. Un nombre n comporte environ log10(n) + 1 chiffres, donc la même borne s’écrit souvent O(log n). Pour un entier de 32 bits, cela représente au maximum 10 étapes.

Comment obtenir les chiffres d’un nombre sans le convertir en chaîne de caractères ?

Utilisez le reste et la division entière par 10. n % 10 est le dernier chiffre, et diviser n par 10 en supprimant le reste élimine ce chiffre. Répétez jusqu’à ce que n atteigne 0, et vous parcourrez chaque chiffre de droite à gauche.

Quelle est la racine numérique d’un nombre ?

C’est ce que l’on obtient en additionnant les chiffres encore et encore jusqu’à ce qu’il n’en reste qu’un : 9045 donne 18, puis 9. Pour un n positif, cela équivaut à 1 + (n-1) % 9, car tout nombre a le même reste lorsqu’on le divise par 9 que la somme de ses chiffres.

La version chaîne de caractères ou la version arithmétique est-elle meilleure ?

Les deux sont en O(d) et les deux sont correctes. La version avec une chaîne de caractères est plus courte à écrire dans de nombreux langages, mais crée une copie des chiffres. La version arithmétique utilise O(1) de mémoire supplémentaire et montre à l’intervieweur que tu sais comment % 10 et / 10 décomposent un nombre, ce qui est utile dans les problèmes de palindrome et d’inversion des chiffres.

Python

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

Cas de test

Cas 1

Cas 2

Entrée

n = 9045

Attendu