Palindrome Number

Q: Un nombre négatif est-il un palindrome ?

Non. Lu à l’envers, -121 devient 121- , et le signe moins n’a pas de caractère correspondant à l’autre extrémité. Ainsi, tout entier négatif renvoie false .

Q: Quelle est la complexité temporelle du problème du nombre palindrome ?

Les deux approches s’exécutent en O(log x) temps, car un nombre x comporte environ log10(x) chiffres, et chacun est traité une fois. L’approche par chaîne utilise un espace supplémentaire de O(log x) pour le texte ; l’inversion de la moitié utilise O(1) .

FacileMaths et simulation

+10

Un nombre est un palindrome lorsque ses chiffres se lisent de la même manière de gauche à droite et de droite à gauche, comme 1221. Étant donné un entier x, renvoie true s’il s’agit d’un palindrome et false dans le cas contraire. Un nombre négatif n’est jamais considéré comme tel, car son signe moins n’a pas de correspondant à l’autre extrémité.

Fonction

isPalindrome(x: integer) → boolean

xinteger: l’entier à vérifier, éventuellement négatif
Renvoieboolean: vrai si x se lit dans les deux sens, faux sinon

Contraintes

-2³¹ ≤ x ≤ 2³¹-1
Tout nombre négatif renvoie false.

Exemples

Entrée: x = 121
Sortie: true
Explication: Lu à l’envers, 121 reste 121, donc la réponse est true.

Entrée: x = -121
Sortie: false
Explication: En le lisant à l’envers, -121 devient 121-, ce qui constitue un texte différent. La réponse est donc false.

Pour aller plus loin

Peux-tu le résoudre sans convertir l’entier en chaîne de caractères ?

Indices

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

0 sur 3 ouverts

Solution

Un nombre est un palindrome lorsqu’il est égal à son propre inverse. Sous forme de texte, cela se vérifie en une seule comparaison. Sans texte, reconstruire le nombre entier à l’envers peut provoquer un dépassement de capacité ; inverse donc uniquement la seconde moitié des chiffres et compare-la à la première moitié.

Comparez la chaîne à son inverse

Intuition

Écrivez le nombre sous forme de texte et comparez-le à son inverse. Les nombres négatifs ne nécessitent aucun cas particulier : -121 commence par un signe moins et se termine par un chiffre, il n’est donc jamais égal à son inverse 121-.

Le texte comporte un caractère par chiffre, soit environ log10(x) caractères, et au maximum 11 ici. Le coût correspond à la chaîne supplémentaire.

Algorithme

Convertis x en une chaîne s.
Inverse s.
Renvoie si s est égal à son inverse.

def isPalindrome(x):
    s = str(x)
    # A minus sign sits only at the front, so a negative never matches its reverse.
    return s == s[::-1]

Inverser la moitié du nombre

Intuition

x % 10 donne le dernier chiffre, et la division entière par 10 le supprime. Déplacer les chiffres de la fin de x vers un deuxième nombre half permet de construire l’inverse des chiffres supprimés. Arrête-toi lorsque half est supérieur ou égal à ce qu’il reste de x : tu as pris la moitié des chiffres. 1221 se termine avec x = 12 et half = 12, un palindrome. Avec un nombre impair de chiffres, half contient aussi le chiffre du milieu : 12321 se termine avec x = 12 et half = 123, donc tu compares x à half / 10.

Traite deux cas avant la boucle. Un nombre négatif n’est jamais un palindrome. Un nombre qui se termine par 0 devrait commencer par 0, ce qui n’est le cas que de 0 ; sans cette vérification, 10 se termine avec x = 0 et half = 1, et x == half / 10 est vraie par erreur. half ne dépasse jamais 6 chiffres, il tient donc dans n’importe quel type entier.

Algorithme

Si x est négatif, ou se termine par 0 sans être égal à 0, retourne false.
Définis half = 0.
Tant que x > half, définis half = half * 10 + x % 10 et divise x par 10 avec une division entière.
Retourne true si x == half (nombre de chiffres pair) ou x == half / 10 (nombre de chiffres impair).

def isPalindrome(x):
    if x < 0:
        return False
    original, reversed_num = x, 0
    while x > 0:
        reversed_num = reversed_num * 10 + x % 10
        x //= 10
    return original == reversed_num

Pièges et cas limites

Oublier les nombres négatifs. Dans les langages où le reste conserve le signe, inverser -121 donne -121 et la vérification réussit. En Python, où -1 // 10 vaut -1, une boucle while x != 0 ne se termine jamais.
Ne pas rejeter les nombres qui se terminent par 0. L’inversion de la moitié accepte alors 10. 0 est lui-même un palindrome.
Inverser le nombre entier dans un entier de 32 bits. L’inverse de 2147483647 ne tient pas.
Utiliser / dans un langage où la division donne une fraction. Utilisez Math.floor(x / 10) en JavaScript, // en Python, %/% en R et ~/ en Dart.
Comparer l’inverse complet à x après que la boucle a modifié x. Conservez une copie de la valeur d’origine.

Questions fréquentes3

Un nombre négatif est-il un palindrome ?

Non. Lu à l’envers, -121 devient 121-, et le signe moins n’a pas de caractère correspondant à l’autre extrémité. Ainsi, tout entier négatif renvoie false.

Pourquoi inverser seulement la moitié du nombre ?

Inverser tous les chiffres peut provoquer un dépassement de capacité d’un entier de 32 bits : l’inverse de 2147483647 est supérieur au plus grand int. La moitié des chiffres tient toujours, et la boucle effectue la moitié du travail.

Quelle est la complexité temporelle du problème du nombre palindrome ?

Les deux approches s’exécutent en O(log x) temps, car un nombre x comporte environ log10(x) chiffres, et chacun est traité une fois. L’approche par chaîne utilise un espace supplémentaire de O(log x) pour le texte ; l’inversion de la moitié utilise O(1).

def isPalindrome(x):
    # Écrivez le code ici

Test #1

Test #2

Argument

x = 121

Résultat attendu

true