Count Digits

Q: Pourquoi 0 a-t-il un chiffre ?

Zéro s’écrit avec le seul caractère 0 , sa forme décimale comporte donc un chiffre. Le code qui compte les divisions tant que le nombre est supérieur à 0 ne s’exécute jamais pour 0 et renvoie 0. Initialiser le compteur à 1 et diviser tant que le nombre est supérieur ou égal à 10 permet de traiter ce cas sans condition particulière.

Q: Peux-tu utiliser log10 pour compter les chiffres d’un nombre ?

Pour un n positif, le nombre de chiffres est floor(log10(n)) + 1 , mais le logarithme est calculé en virgule flottante. Il n’est pas défini pour 0 et, à proximité d’une puissance de dix, il peut être arrondi dans le mauvais sens : log10(10^15-1) donne exactement 15 en double précision. La division entière donne toujours la réponse exacte.

Q: Quelle est la complexité temporelle du comptage des chiffres ?

Un nombre n comporte floor(log10(n)) + 1 chiffres, et la boucle effectue une division par chiffre, donc elle s’exécute en O(log n) temps. Pour un entier de 32 bits, cela représente au maximum 10 étapes.

DébutantMaths et simulation

+10

Écrivez une fonction qui reçoit un entier non négatif n et renvoie le nombre de chiffres qu’il comporte lorsqu’on l’écrit en base 10 sans zéros initiaux. Zéro s’écrit avec un seul 0, il comporte donc un chiffre.

Fonction

countDigits(n: integer) → integer

ninteger: l’entier non négatif à mesurer
Renvoieinteger: le nombre de chiffres décimaux dans n

Contraintes

0 ≤ n ≤ 2³¹-1

Exemples

Entrée: n = 4096
Sortie: 4
Explication: La division entière par 10 transforme 4096 en 409, 40 et 4. Cela enlève trois chiffres et en laisse un, donc la réponse est 4.

Entrée: n = 0
Sortie: 1
Explication: 0 s’écrit avec un seul chiffre. Une boucle qui compte tant que le nombre est supérieur à 0 ne s’exécute jamais ici et renverrait 0 au lieu de 1.

Entrée: n = 100
Sortie: 3
Explication: Les zéros sont aussi des chiffres : 100 s’écrit 1, 0, 0, donc la réponse est 3.

+16 tests cachés à la soumission

Pour aller plus loin

Peux-tu compter les chiffres sans utiliser une boucle qui s’exécute une fois par chiffre, par exemple en effectuant une recherche dichotomique parmi les puissances de dix ?

Indices

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

0 sur 3 ouverts

Solution

Le nombre de chiffres correspond au nombre de fois où l’on peut diviser par 10 avant qu’il ne reste qu’un chiffre, plus ce chiffre. L’idée tient sur une ligne ; le travail réside dans les cas limites. 0 a un chiffre, le compte change entre 9 et 10, et une formule basée sur un logarithme échoue pour 0 et, en virgule flottante, un peu en dessous des grandes puissances de dix.

Écrivez le nombre en toutes lettres et comptez les caractères

Intuition

Ton langage sait déjà écrire n en décimal. Demande-lui cette chaîne et compte les caractères : 4096 devient "4096", soit quatre caractères. 0 devient "0", soit un caractère, donc zéro ne nécessite aucun cas particulier.

La conversion divise par 10 dans la bibliothèque, une fois par chiffre, donc le travail est de O(log n). La chaîne contient un caractère par chiffre, ce qui représente O(log n) de mémoire supplémentaire, soit au plus 10 caractères ici.

Le formatage doit être en décimal simple. En R, as.character(1e5) donne "1e+05", soit cinq caractères pour un nombre à six chiffres ; utilise donc sprintf("%.0f", n). Dans Lua 5.3 et les versions ultérieures, tostring(4096.0) conserve le .0, tandis que string.format("%d", n) écrit l’entier dans toutes les versions.

Algorithme

Convertis n en chaîne décimale avec une fonction qui ne passe jamais en notation scientifique.
Compte les caractères de la chaîne.
Renvoie ce nombre. Pour 0, la chaîne est "0", donc la réponse est 1 sans vérification supplémentaire.

def countDigits(n):
    return len(str(n))

Divise par 10 jusqu’à ce qu’il ne reste qu’un chiffre

Intuition

La division entière par 10 supprime le dernier chiffre : 4096 / 10 donne 409. Chaque division enlève un chiffre, donc le nombre de divisions nécessaires pour atteindre un seul chiffre, plus un pour ce dernier chiffre, donne la réponse. 4096 nécessite trois divisions (409, 40, 4), il a donc 4 chiffres.

Commence le décompte à 1 et divise tant que n ≥ 10. Commencer à 1 signifie que chaque nombre possède au moins un chiffre, ce qui correspond exactement à la règle pour 0. La version qu’on écrit d’abord, qui compte à partir de 0 tant que n > 0, renvoie 0 pour n = 0 et nécessite une vérification distincte.

La boucle s’exécute une fois par chiffre après le premier, au plus 9 fois pour 2147483647, donc elle prend un temps de O(log n). Elle conserve un compteur et modifie sa propre copie de n, ce qui nécessite un espace supplémentaire de O(1).

Algorithme

Définis count = 1, pour le chiffre qui est toujours présent.
Tant que n ≥ 10, divise n par 10 en utilisant la division entière et ajoute 1 à count.
Lorsqu'il ne reste qu'un chiffre, renvoie count.

def countDigits(n):
    count = 1  # every number, 0 included, has at least one digit
    while n >= 10:
        n //= 10
        count += 1
    return count

Pièges et cas limites

Chaque bogue de ce problème se situe à une limite.

Compter à partir de 0 tant que n > 0. Cela convient à tout nombre positif et renvoie 0 pour n = 0.
Utiliser floor(log10(n)) + 1. Cette méthode échoue avec 0, dont le logarithme est moins l’infini, et avec les grandes valeurs juste en dessous d’une puissance de dix : en double précision, log10(10^15-1) est arrondi exactement à 15, donc la formule indique 16 chiffres au lieu de 15.
Utiliser la division réelle dans une boucle qui s’exécute tant que n > 0. En JavaScript, Lua, PHP et R, / conserve la partie fractionnaire, donc 4096 tend vers 0 pendant 328 étapes avant de l’atteindre. Utilisez Math.floor, math.floor, intdiv ou %/%.
Utiliser la notation scientifique dans la version avec chaîne de caractères : R écrit 100000 sous la forme "1e+05".
Compter le signe moins comme un chiffre. Ici, l’entrée n’est jamais négative, mais String(-42) comporte trois caractères ; une version prenant en charge les nombres négatifs commence donc par prendre la valeur absolue.

Questions fréquentes4

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

Divisez-le par 10 avec une division entière jusqu’à ce qu’il ne reste qu’un chiffre, en comptant les divisions, puis ajoutez 1 pour le dernier chiffre. 4096 devient 409, 40, 4 : trois divisions, donc 4 chiffres. La boucle utilise un espace supplémentaire de O(1).

Pourquoi 0 a-t-il un chiffre ?

Zéro s’écrit avec le seul caractère 0, sa forme décimale comporte donc un chiffre. Le code qui compte les divisions tant que le nombre est supérieur à 0 ne s’exécute jamais pour 0 et renvoie 0. Initialiser le compteur à 1 et diviser tant que le nombre est supérieur ou égal à 10 permet de traiter ce cas sans condition particulière.

Peux-tu utiliser log10 pour compter les chiffres d’un nombre ?

Pour un n positif, le nombre de chiffres est floor(log10(n)) + 1, mais le logarithme est calculé en virgule flottante. Il n’est pas défini pour 0 et, à proximité d’une puissance de dix, il peut être arrondi dans le mauvais sens : log10(10^15-1) donne exactement 15 en double précision. La division entière donne toujours la réponse exacte.

Quelle est la complexité temporelle du comptage des chiffres ?

Un nombre n comporte floor(log10(n)) + 1 chiffres, et la boucle effectue une division par chiffre, donc elle s’exécute en O(log n) temps. Pour un entier de 32 bits, cela représente au maximum 10 étapes.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

n = 4096

Attendu