Palindrome Number

Q: ¿Es un número negativo un palíndromo?

No. Si lo lees al revés, -121 se convierte en 121- , y el signo menos no tiene un carácter correspondiente en el otro extremo. Así que todos los enteros negativos devuelven false .

Q: ¿Cuál es la complejidad temporal de Palindrome Number?

Ambos enfoques se ejecutan en tiempo O(log x) , porque un número x tiene aproximadamente log10(x) dígitos y cada uno se procesa una vez. El enfoque con cadenas usa espacio adicional O(log x) para el texto; la inversión de la mitad usa O(1) .

FácilMatemáticas y simulación

+10

Un número es un palíndromo cuando sus dígitos se leen igual de izquierda a derecha y de derecha a izquierda, como 1221. Dado un entero x, devuelve true si es un palíndromo y false en caso contrario. Un número negativo nunca cuenta, porque su signo menos no tiene otro igual en el extremo opuesto.

Función

isPalindrome(x: integer) → boolean

xinteger: el entero que se debe comprobar, posiblemente negativo
Devuelveboolean: true si x se lee igual en ambas direcciones, false en caso contrario

Restricciones

-2³¹ ≤ x ≤ 2³¹-1
Todo número negativo devuelve false.

Ejemplos

Entrada: x = 121
Salida: true
Explicación: Leído al revés, 121 sigue siendo 121, así que la respuesta es true.

Entrada: x = -121
Salida: false
Explicación: Leído al revés, -121 se convierte en 121-, que es un texto diferente, así que la respuesta es false.

Para ir más allá

¿Puedes resolverlo sin convertir el entero en una cadena?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un número es un palíndromo cuando es igual a sí mismo al revés. Como texto, eso es una comparación. Sin texto, reconstruir el número completo invertido puede causar un desbordamiento, así que invierte solo la segunda mitad de los dígitos y compárala con la primera mitad.

Compara la cadena con su reverso

Intuición

Escribe el número como texto y compáralo con su reverso. Los números negativos no necesitan un caso especial: -121 empieza con un signo menos y termina con un dígito, así que nunca es igual a su reverso 121-.

El texto tiene un carácter por dígito, aproximadamente log10(x) caracteres y como máximo 11 aquí. El costo es la cadena adicional.

Algoritmo

Convierte x en una cadena s.
Invierte s.
Devuelve si s es igual a su inversa.

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]

Invierte la mitad del número

Intuición

x % 10 da el último dígito, y la división entera entre 10 lo elimina. Al mover los dígitos del final de x a un segundo número half, se forma el reverso de los dígitos eliminados. Detente cuando half sea al menos igual a lo que queda de x: habrás tomado la mitad de los dígitos. 1221 termina con x = 12 y half = 12, un palíndromo. Si el número de dígitos es impar, half también contiene el dígito del medio: 12321 termina con x = 12 y half = 123, así que comparas x con half / 10.

Resuelve dos casos antes del bucle. Un número negativo nunca es un palíndromo. Un número que termina en 0 tendría que empezar con 0, y eso solo ocurre con el 0; sin esta comprobación, 10 termina con x = 0 y half = 1, y x == half / 10 se cumple por error. half nunca supera los 6 dígitos, así que cabe en cualquier tipo entero.

Algoritmo

Si x es negativo o termina en 0 y no es 0, devuelve false.
Establece half = 0.
Mientras x > half, establece half = half * 10 + x % 10 y divide x entre 10 usando división entera.
Devuelve true si x == half (cantidad par de dígitos) o x == half / 10 (cantidad impar de dígitos).

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

Errores comunes y casos límite

Olvidar los negativos. En los lenguajes cuyo resto conserva el signo, invertir -121 da -121 y la comprobación se cumple. En Python, donde -1 // 10 es -1, un bucle while x != 0 nunca termina.
No rechazar los números que terminan en 0. La inversión de la mitad acepta entonces 10. 0 en sí mismo es un palíndromo.
Invertir el número completo en un entero de 32 bits. La inversión de 2147483647 no cabe.
Usar / cuando el lenguaje divide con una fracción. Usa Math.floor(x / 10) en JavaScript, // en Python, %/% en R y ~/ en Dart.
Comparar la inversión completa con x después de que el bucle haya cambiado x. Conserva una copia del valor original.

Preguntas frecuentes3

¿Es un número negativo un palíndromo?

No. Si lo lees al revés, -121 se convierte en 121-, y el signo menos no tiene un carácter correspondiente en el otro extremo. Así que todos los enteros negativos devuelven false.

¿Por qué invertir solo la mitad del número?

Invertir todos los dígitos puede provocar un desbordamiento de un entero de 32 bits: el reverso de 2147483647 es mayor que el valor máximo de int. La mitad de los dígitos siempre cabe, y el bucle hace la mitad del trabajo.

¿Cuál es la complejidad temporal de Palindrome Number?

Ambos enfoques se ejecutan en tiempo O(log x), porque un número x tiene aproximadamente log10(x) dígitos y cada uno se procesa una vez. El enfoque con cadenas usa espacio adicional O(log x) para el texto; la inversión de la mitad usa O(1).

def isPalindrome(x):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumento

x = 121

Salida Esperada

true