¿Cómo verifico si un número es un palíndromo?

¿Cómo verifico si un número es un palíndromo?

Cualquier idioma. Cualquier algoritmo (excepto el algoritmo de convertir el número en una cadena y luego invertir la cadena).

Este es uno de los problemas del Proyecto Euler . Cuando lo resolví en Haskell, hice exactamente lo que sugieres, convertir el número en una cadena. Entonces es trivial comprobar que la cadena es un palíndromo. Si funciona lo suficientemente bien, ¿por qué molestarse en hacerlo más complejo? Ser un palíndromo es una propiedad léxica más que matemática.

Para cualquier número dado:

n = num;
rev = 0;
while (num > 0)
{
    dig = num % 10;
    rev = rev * 10 + dig;
    num = num / 10;
}

Si n == reventonces numes un palíndromo:

cout << "Number " << (n == rev ? "IS" : "IS NOT") << " a palindrome" << endl;

def ReverseNumber(n, partial=0):
    if n == 0:
        return partial
    return ReverseNumber(n // 10, partial * 10 + n % 10)

trial = 123454321
if ReverseNumber(trial) == trial:
    print("It's a Palindrome!")

Funciona solo para enteros. No está claro a partir del enunciado del problema si se deben considerar los números de coma flotante o los ceros iniciales.

Por encima de la mayoría de las respuestas que tienen un problema trivial es que la variable int posiblemente podría desbordarse.

Consulte http://articles.leetcode.com/palindrome-number/

boolean isPalindrome(int x) {
    if (x < 0)
        return false;
    int div = 1;
    while (x / div >= 10) {
        div *= 10;
    }
    while (x != 0) {
        int l = x / div;
        int r = x % 10;
        if (l != r)
            return false;
        x = (x % div) / 10;
        div /= 100;
    }
    return true;
}

int is_palindrome(unsigned long orig)
{
    unsigned long reversed = 0, n = orig;

    while (n > 0)
    {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }

    return orig == reversed;
}

Empuje cada dígito individual en una pila, luego sáquelos. Si es lo mismo hacia adelante y hacia atrás, es un palíndromo.

No noté ninguna respuesta que resolviera este problema sin usar espacio adicional, es decir, todas las soluciones que vi usaban una cadena u otro número entero para revertir el número u otras estructuras de datos.

Aunque los lenguajes como Java se desbordan en el desbordamiento de enteros, este comportamiento no está definido en lenguajes como C. ( Intente revertir 2147483647 (Integer.MAX_VALUE) en Java ) La
solución podría ser usar un largo o algo pero, estilísticamente, no lo sé como ese enfoque

Ahora, el concepto de un número palindrómico es que el número debe leer el mismo hacia adelante y hacia atrás. Excelente. Con esta información, podemos comparar el primer dígito y el último dígito. El truco es que, para el primer dígito, necesitamos el orden del número. Digamos, 12321. Dividir esto entre 10000 nos daría el primer 1. El 1 posterior se puede recuperar tomando el mod con 10. Ahora, para reducir esto a 232 (12321 % 10000)/10 = (2321)/10 = 232.. Y ahora, el 10000 necesitaría ser reducido por un factor de 2. Entonces, ahora al código Java ...

private static boolean isPalindrome(int n) {
    if (n < 0)
        return false;

    int div = 1;
    // find the divisor
    while (n / div >= 10)
        div *= 10;

    // any number less than 10 is a palindrome
    while (n != 0) {
        int leading = n / div;
        int trailing = n % 10;
        if (leading != trailing)
            return false;

        // % with div gets rid of leading digit
        // dividing result by 10 gets rid of trailing digit
        n = (n % div) / 10;

        // got rid of 2 numbers, update div accordingly
        div /= 100;
    }
    return true;
}

Editado según la sugerencia de Hardik para cubrir los casos donde hay ceros en el número.

En Python, hay una forma rápida e iterativa.

def reverse(n):
    newnum=0
    while n>0:
        newnum = newnum*10 + n % 10
        n//=10
    return newnum

def palindrome(n):
    return n == reverse(n)

Esto también evita problemas de memoria con recursividad (como el error StackOverflow en Java)

La forma más rápida que sé:

bool is_pal(int n) {
    if (n % 10 == 0) return 0;
    int r = 0;
    while (r < n) {
        r = 10 * r + n % 10;
        n /= 10;
    }
    return n == r || n == r / 10;
}

Solo por diversión, este también funciona.

a = num;
b = 0;
if (a % 10 == 0)
  return a == 0;
do {
  b = 10 * b + a % 10;
  if (a == b)
    return true;
  a = a / 10;
} while (a > b);
return a == b;

excepto convertir el número en una cadena y luego invertir la cadena.

¿Por qué descartar esa solución? Es fácil de implementar y legible . Si le preguntaron sin computadora a mano si 2**10-23es un palíndromo decimal, seguramente lo probaría escribiéndolo en decimal.

Al menos en Python, el eslogan 'las operaciones de cadena son más lentas que la aritmética' es realmente falso. Comparé el algoritmo aritmético de Smink con una simple inversión de cadenaint(str(i)[::-1]) . No hubo diferencias significativas en la velocidad: sucedió que la inversión de la cuerda fue marginalmente más rápida.

En lenguajes compilados (C / C ++), el eslogan puede mantenerse, pero uno corre el riesgo de errores de desbordamiento con grandes números.

def reverse(n):
    rev = 0
    while n > 0:
        rev = rev * 10 + n % 10
        n = n // 10
    return rev

upper = 10**6

def strung():
    for i in range(upper):
        int(str(i)[::-1])

def arithmetic():
    for i in range(upper):
        reverse(i)

import timeit
print "strung", timeit.timeit("strung()", setup="from __main__ import strung", number=1)
print "arithmetic", timeit.timeit("arithmetic()", setup="from __main__ import arithmetic", number=1)

Resultados en segundos (menos es mejor):

ensartado 1.50960231881 aritmética 1.69729960569

Respondí el problema de Euler de una manera muy brutal. Naturalmente, había un algoritmo mucho más inteligente en la pantalla cuando llegué al nuevo hilo del foro asociado desbloqueado. A saber, un miembro que se hizo cargo de Begoner tenía un enfoque tan novedoso que decidí volver a implementar mi solución usando su algoritmo. Su versión estaba en Python (usando bucles anidados) y la volví a implementar en Clojure (usando un solo bucle / recur).

Aquí para tu diversión:

(defn palindrome? [n]
  (let [len (count n)]
    (and
      (= (first n) (last n))
      (or (>= 1 (count n))
        (palindrome? (. n (substring 1 (dec len))))))))

(defn begoners-palindrome []
  (loop [mx 0
         mxI 0
         mxJ 0
         i 999
         j 990]
    (if (> i 100)
      (let [product (* i j)]
        (if (and (> product mx) (palindrome? (str product)))
          (recur product i j
            (if (> j 100) i (dec i))
            (if (> j 100) (- j 11) 990))
          (recur mx mxI mxJ
            (if (> j 100) i (dec i))
            (if (> j 100) (- j 11) 990))))
      mx)))

(time (prn (begoners-palindrome)))

También hubo respuestas de Common Lisp, pero fueron indescifrables para mí.

Aquí hay una versión de Scheme que construye una función que funcionará contra cualquier base. Tiene una verificación de redundancia: devuelve falso rápidamente si el número es un múltiplo de la base (termina en 0).
Y no reconstruye todo el número invertido, solo la mitad.
Eso es todo lo que necesitamos.

(define make-palindrome-tester
   (lambda (base)
     (lambda (n)
       (cond
         ((= 0 (modulo n base)) #f)
         (else
          (letrec
              ((Q (lambda (h t)
                    (cond
                      ((< h t) #f)
                      ((= h t) #t)
                      (else
                       (let*
                           ((h2 (quotient h base))
                            (m  (- h (* h2 base))))
                         (cond
                           ((= h2 t) #t)
                           (else
                            (Q h2 (+ (* base t) m))))))))))
            (Q n 0)))))))

Solución recursiva en rubí, sin convertir el número a cadena.

def palindrome?(x, a=x, b=0)
  return x==b if a<1
  palindrome?(x, a/10, b*10 + a%10)
end

palindrome?(55655)

Versión de Golang:

package main

import "fmt"

func main() {
    n := 123454321
    r := reverse(n)
    fmt.Println(r == n)
}

func reverse(n int) int {
    r := 0
    for {
        if n > 0 {
            r = r*10 + n%10
            n = n / 10
        } else {
            break
        }
    }
    return r
}

Saque el primer y último dígito y compárelos hasta que se agote. Puede haber un dígito a la izquierda, o no, pero de cualquier manera, si todos los dígitos aparecidos coinciden, es un palíndromo.

Aquí hay una solución más en c ++ usando plantillas. Esta solución funcionará para la comparación de cadenas de palíndromo insensible a mayúsculas y minúsculas.

template <typename bidirection_iter>
bool palindrome(bidirection_iter first, bidirection_iter last)
{
    while(first != last && first != --last)
    {
        if(::toupper(*first) != ::toupper(*last))
            return false;
        else
            first++;
    }
    return true;
}

Un método con un factor constante un poco mejor que el método @sminks:

num=n
lastDigit=0;
rev=0;
while (num>rev) {
    lastDigit=num%10;
    rev=rev*10+lastDigit;
    num /=2;
}
if (num==rev) print PALINDROME; exit(0);
num=num*10+lastDigit; // This line is required as a number with odd number of bits will necessary end up being smaller even if it is a palindrome
if (num==rev) print PALINDROME

Aquí hay una versión #

let reverseNumber n =
    let rec loop acc = function
    |0 -> acc
    |x -> loop (acc * 10 + x % 10) (x/10)    
    loop 0 n

let isPalindrome = function
    | x  when x = reverseNumber x -> true
    | _ -> false

Un número es palindrómico si su representación de cadena es palindrómica:

def is_palindrome(s):
    return all(s[i] == s[-(i + 1)] for i in range(len(s)//2))

def number_palindrome(n):
    return is_palindrome(str(n))

def palindrome(n):
    d = []
    while (n > 0):
        d.append(n % 10)
        n //= 10
    for i in range(len(d)/2):
        if (d[i] != d[-(i+1)]):
            return "Fail."
    return "Pass."

Para verificar el número dado es Palindrome o no (Código Java)

class CheckPalindrome{
public static void main(String str[]){
        int a=242, n=a, b=a, rev=0;
        while(n>0){
                    a=n%10;  n=n/10;rev=rev*10+a;
                    System.out.println(a+"  "+n+"  "+rev);  // to see the logic
               }
        if(rev==b)  System.out.println("Palindrome");
        else        System.out.println("Not Palindrome");
    }
}

Muchas de las soluciones publicadas aquí invierten el número entero y lo almacenan en una variable que usa espacio adicional O(n), pero aquí hay una solución con O(1)espacio.

def isPalindrome(num):
    if num < 0:
        return False
    if num == 0:
        return True
    from math import log10
    length = int(log10(num))
    while length > 0:
        right = num % 10
        left = num / 10**length
        if right != left:
            return False
        num %= 10**length
        num /= 10
        length -= 2
    return True

Siempre uso esta solución de Python debido a su tamaño compacto.

def isPalindrome(number):
    return int(str(number)[::-1])==number

Prueba esto:

reverse = 0;
    remainder = 0;
    count = 0;
    while (number > reverse)
    {
        remainder = number % 10;
        reverse = reverse * 10 + remainder;
        number = number / 10;
        count++;
    }
    Console.WriteLine(count);
    if (reverse == number)
    {
        Console.WriteLine("Your number is a palindrome");
    }
    else
    {
        number = number * 10 + remainder;
        if (reverse == number)
            Console.WriteLine("your number is a palindrome");
        else
            Console.WriteLine("your number is not a palindrome");
    }
    Console.ReadLine();
}
}

Aquí hay una solución que usa listas como pilas en python:

def isPalindromicNum(n):
    """
        is 'n' a palindromic number?
    """
    ns = list(str(n))
    for n in ns:
        if n != ns.pop():
            return False
    return True

hacer estallar la pila solo considera el lado derecho del número para la comparación y falla rápidamente para reducir los cheques

 public class Numbers
 {
   public static void main(int givenNum)
   { 
       int n= givenNum
       int rev=0;

       while(n>0)
       {
          //To extract the last digit
          int digit=n%10;

          //To store it in reverse
          rev=(rev*10)+digit;

          //To throw the last digit
          n=n/10;
      }

      //To check if a number is palindrome or not
      if(rev==givenNum)
      { 
         System.out.println(givenNum+"is a palindrome ");
      }
      else
      {
         System.out.pritnln(givenNum+"is not a palindrome");
      }
  }
}

let isPalindrome (n:int) =
   let l1 = n.ToString() |> List.ofSeq |> List.rev
   let rec isPalindromeInt l1 l2 =
       match (l1,l2) with
       | (h1::rest1,h2::rest2) -> if (h1 = h2) then isPalindromeInt rest1 rest2 else false
       | _ -> true
   isPalindromeInt l1 (n.ToString() |> List.ofSeq)

checkPalindrome(int number)
{
    int lsd, msd,len;
    len = log10(number);
    while(number)
    {
        msd = (number/pow(10,len)); // "most significant digit"
        lsd = number%10; // "least significant digit"
        if(lsd==msd)
        {
            number/=10; // change of LSD
            number-=msd*pow(10,--len); // change of MSD, due to change of MSD
            len-=1; // due to change in LSD
            } else {return 1;}
    }
    return 0;
}

La forma recursiva, no muy eficiente, solo proporciona una opción

(Código de Python)

def isPalindrome(num):
    size = len(str(num))
    demoninator = 10**(size-1)
    return isPalindromeHelper(num, size, demoninator)

def isPalindromeHelper(num, size, demoninator):
    """wrapper function, used in recursive"""
    if size <=1:
        return True
    else:       
        if num/demoninator != num%10:
            return False
        # shrink the size, num and denominator
        num %= demoninator
        num /= 10
        size -= 2
        demoninator /=100
        return isPalindromeHelper(num, size, demoninator)