Reverse the Digits

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

Répète deux étapes jusqu’à ce que le nombre soit 0 : récupère le dernier chiffre avec n % 10 et ajoute-le au résultat avec result = result * 10 + digit , puis supprime-le avec n = n / 10 en utilisant la division entière. Pour 1234 , le résultat augmente ainsi : 4, 43, 432 et 4321.

DébutantMaths et simulation

+10

On vous donne un entier non négatif n. Renvoyez le nombre obtenu en écrivant ses chiffres décimaux dans l’ordre inverse. Les zéros qui se retrouvent au début sont supprimés, donc 120 devient 21.

Fonction

reverseDigits(n: integer) → integer

ninteger: l’entier non négatif à inverser
Renvoieinteger: les chiffres de n en ordre inverse, sous forme de nombre

Contraintes

0 ≤ n < 10⁹
Le nombre inversé tient également dans un entier signé sur 32 bits.

Exemples

Entrée: n = 1234
Sortie: 4321
Explication: Les chiffres de 1234 sont 1, 2, 3 et 4. Lus depuis la fin, ils sont 4, 3, 2 et 1, ce qui donne 4321.

Entrée: n = 120
Sortie: 21
Explication: Lu en sens inverse, 120 donne les chiffres 0, 2 et 1. Un zéro en tête ne compte pas dans un nombre, donc la réponse est 21.

Entrée: n = 0
Sortie: 0
Explication: 0 a un seul chiffre, et le renverser donne à nouveau 0.

+13 tests cachés à la soumission

Pour aller plus loin

Si n peut être n’importe quel entier sur 32 bits, le nombre obtenu en inversant ses chiffres pourrait ne pas être représentable. Comment détecteriez-vous cela avant que la multiplication ne déborde ?

Indices

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

0 sur 3 ouverts

Solution

Inverser le texte décimal tient en une ligne dans la plupart des langages, et c’est une bonne première réponse. Les personnes qui mènent les entretiens demandent généralement ensuite d’obtenir le même résultat sans utiliser de chaînes de caractères. La méthode arithmétique repose sur deux opérations : n % 10 lit le dernier chiffre et n / 10 (division entière) le supprime.

Inverser le texte décimal

Intuition

Les chiffres d’un nombre sont exactement les caractères de son écriture décimale. Transforme n en texte, inverse les caractères, puis reconvertis le texte en nombre. 1234 devient "1234", puis "4321", puis 4321.

Les zéros en tête se gèrent d’eux-mêmes. Inverser 120 donne le texte "021", et l’analyse en tant que nombre ignore le zéro initial et renvoie 21.

Un nombre inférieur à 10^9 comporte au plus 9 chiffres, et le travail ainsi que le texte supplémentaire augmentent avec le nombre de chiffres, soit O(log n).

Algorithme

Convertis n en texte décimal.
Inverse les caractères.
Analyse le texte inversé comme un entier et retourne-le.

def reverseDigits(n):
    # int() ignores the leading zeros that trailing zeros turn into.
    return int(str(n)[::-1])

Ajouter et retirer des chiffres avec des opérations arithmétiques

Intuition

Retire les chiffres à la fin de n un par un et ajoute chacun à la fin d’un nouveau nombre. n % 10 correspond au dernier chiffre de n, et n / 10 avec une division entière le supprime. Pour ajouter un chiffre d à la fin de result, décale d’un rang vers la gauche ce qui s’y trouve et place d au rang des unités : result * 10 + d.

Pour 1234, result prend les valeurs 4, 43, 432, 4321, tandis que n prend les valeurs 123, 12, 1, 0. La boucle s’arrête lorsque n atteint 0 ; elle s’exécute donc une fois par chiffre.

Les zéros initiaux n’apparaissent jamais. Pour 120, le premier chiffre retiré est 0, et 0 * 10 + 0 vaut toujours 0 : il ne laisse donc aucune trace. Pour n = 0, la boucle ne s’exécute jamais et la réponse est 0. Seuls deux entiers sont conservés, donc l’espace supplémentaire est O(1).

Algorithme

Définissez result = 0.
Tant que n est supérieur à 0, calculez le dernier chiffre n % 10.
Définissez result = result * 10 + digit.
Supprimez le chiffre avec n = n / 10, en utilisant la division entière.
Renvoyez result.

def reverseDigits(n):
    result = 0
    while n > 0:
        result = result * 10 + n % 10  # push the last digit of n
        n //= 10                        # drop it from n
    return result

Pièges et cas limites

La plupart des bogues viennent de la division et de la fin de la boucle.

Utiliser une division ordinaire alors qu’il faut une division entière. En JavaScript, Python 3 et Lua, n / 10 donne 123.4, donc n ne redevient jamais un nombre entier et result se remplit de fractions. Utilise Math.floor, // ou la division entière de ton langage.
Écrire la boucle sous la forme while n >= 10. Elle s’arrête avant le dernier chiffre, donc 1234 revient sous la forme 432.
Renvoyer le texte inversé sans le convertir en nombre. "021" n’est pas le nombre 21, et la comparaison avec la réponse attendue échoue.
Formater un double dans R avec as.character. Lorsque n est stocké comme un double, il affiche 100000000 sous la forme 1e+08, et le texte inversé est 80+e1. Utilise format(n, scientific = FALSE).

Questions fréquentes4

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

Répète deux étapes jusqu’à ce que le nombre soit 0 : récupère le dernier chiffre avec n % 10 et ajoute-le au résultat avec result = result * 10 + digit, puis supprime-le avec n = n / 10 en utilisant la division entière. Pour 1234, le résultat augmente ainsi : 4, 43, 432 et 4321.

Que deviennent les zéros à la fin lorsque vous inversez un nombre ?

Ils deviendraient des zéros en tête, qu’un nombre ne possède pas, donc ils disparaissent. Inverser 120 donne 21, et inverser 100000000 donne 1. La boucle arithmétique les élimine d’elle-même, car ajouter 0 à un résultat vide le laisse à 0.

Quelle est la complexité temporelle de l’inversion d’un entier ?

La boucle s’exécute une fois par chiffre décimal, et un nombre n comporte environ log10(n) + 1 chiffres, donc le temps est de O(log n). La version arithmétique utilise un espace supplémentaire de O(1) ; la version avec chaîne stocke les chiffres sous forme de texte, ce qui nécessite O(log n).

Peut-on provoquer un dépassement de capacité en inversant un entier ?

Oui, lorsque l’entrée peut être n’importe quel entier de 32 bits. 1000000009 tient dans la limite, mais son inverse 9000000001 ne tient pas. Ici, n est inférieur à 10^9, donc l’inverse comporte au plus 9 chiffres et tient toujours dans la limite. Avec des entrées plus grandes, vérifie result > (INT_MAX - digit) / 10 avant chaque multiplication.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

n = 1234

Attendu