Count Digits

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 ; elle s’exécute donc en temps O(log n) et utilise un espace O(1) . Pour un entier de 32 bits, cela représente au plus 10 étapes.

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, près 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 est toujours exacte.

DébutantMaths et simulation

+10

Étant donné un entier non négatif n, renvoie le nombre de chiffres qu’il comporte lorsqu’il est écrit en base 10 sans zéros initiaux. Zéro s’écrit avec un seul 0, il a 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 : trois chiffres supprimés et un seul restant, 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 renvoie 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.

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 binaire parmi les puissances de dix ?

Indices

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

0 sur 3 ouverts

Solution

Chaque division entière par 10 supprime un chiffre. Compte les divisions jusqu’à ce qu’il ne reste qu’un chiffre, puis ajoute un pour ce chiffre. Les bogues se nichent aux limites : 0 a un chiffre, et une formule logarithmique échoue pour 0 et juste en dessous des grandes puissances de dix.

Écrivez le nombre sous forme de texte et comptez les caractères

Intuition

Votre langage écrit déjà n en décimal. Demandez cette chaîne et comptez ses caractères : 4096 devient "4096", soit quatre caractères, et 0 devient "0", donc zéro ne nécessite aucun cas particulier.

La conversion effectue une division par chiffre, donc le temps et la mémoire supplémentaire sont tous deux en O(log n), avec au plus 10 caractères ici.

Algorithme

Convertis n en chaîne décimale avec une fonction qui ne bascule 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))

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

Intuition

Commence le comptage à 1 et divise par 10 tant que n ≥ 10, en ajoutant 1 à chaque division. Commencer à 1 signifie que chaque nombre possède au moins un chiffre, ce qui est exactement la règle pour 0 ; aucune vérification distincte n'est donc nécessaire.

La boucle s'exécute au plus 9 fois, pour 2147483647 : temps O(log n). Elle conserve un seul compteur et modifie sa propre copie de n, donc l'espace supplémentaire est O(1).

Algorithme

Définissez count = 1, pour le chiffre qui est toujours présent.
Tant que n ≥ 10, divisez n par 10 avec une division entière et ajoutez 1 à count.
Lorsqu'il ne reste qu'un chiffre, renvoyez 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

Compter à partir de 0 tant que n > 0. Cela renvoie 0 pour n = 0.
Utiliser floor(log10(n)) + 1. Cette méthode échoue pour 0, où le logarithme vaut moins l’infini, et pour 10^15-1, où la double précision arrondit le logarithme à exactement 15 et la formule indique 16 chiffres.
La division réelle en JavaScript, Lua, PHP ou R, où / conserve la partie fractionnaire. Une boucle tant que n > 0 s’exécute alors 328 fois pour 4096. Utilisez Math.floor, math.floor, intdiv ou %/%.
La notation scientifique dans la version chaîne. R écrit as.character(1e5) sous la forme "1e+05" ; utilisez sprintf("%.0f", n). Dans Lua 5.3 et les versions ultérieures, tostring(4096.0) conserve le .0 ; utilisez string.format("%d", n).

Questions fréquentes3

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 ; elle s’exécute donc en temps O(log n) et utilise un espace O(1). Pour un entier de 32 bits, cela représente au plus 10 étapes.

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, près 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 est toujours exacte.

Comment compter les chiffres d’un nombre négatif ?

Commence par prendre la valeur absolue, puis compte comme d’habitude. String(-42) contient trois caractères, car le signe moins n’est pas un chiffre. Pour le plus petit entier sur 32 bits, prends la valeur absolue dans un type sur 64 bits, car il ne tient pas sur 32 bits.

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

Test #1

Test #2

Test #3

Argument

n = 4096

Résultat attendu