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

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

Cualquier idioma. Algún algoritmo. (excepto el algoritmo de hacer que el número sea una cadena y luego invertir la cadena).

Este es uno de los problemas de Project Euler . Cuando lo resolví en Haskell, hice exactamente lo que sugeriste, convertí el número a String. Entonces es trivial verificar que la cuerda sea un pallindrome. Si funciona bien, ¿por qué molestarse en hacerlo más complejo? Ser un pallindrome 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 == rev entonces num es 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 en el enunciado del problema si se deben tener en cuenta los números de coma flotante o los ceros a la izquierda.

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://leetcode.com/2012/01/palindrome-number.html

 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; } 

Empuja cada dígito individual en una stack, luego apártalos. Si es lo mismo hacia adelante y hacia atrás, es un palíndromo.

No noté ninguna respuesta que resolvió este problema sin espacio adicional, es decir, todas las soluciones que vi utilizaban una cadena u otro entero para invertir el número o algunas otras estructuras de datos.

Aunque los lenguajes como Java envuelven el desbordamiento de enteros, este comportamiento no está definido en lenguajes como C. [ Intente invertir 2147483647 (Integer.MAX_VALUE) en Java ] Solución podría ser utilizar un largo o algo así, pero, estilísticamente, no lo hago del todo como ese enfoque.

Ahora, el concepto de un número palindrómico es que el número debe leer lo mismo hacia adelante y hacia atrás. Estupendo. Usando 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 por 10000 nos llevaría a la posición 1. El trailing 1 puede recuperarse tomando la modificación con 10. Ahora, para reducir esto a 232. (12321 % 10000)/10 = (2321)/10 = 232 . Y ahora, el 10000 necesitaría reducirse en un factor de 2. Entonces, ahora en el código de 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.

excepto hacer que el número sea una cadena y luego invertir la cadena.

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

En Python al menos, 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 la inversión de cadena simple int(str(i)[::-1]) . No hubo una diferencia significativa en la velocidad; sucedió que la inversión de la cuerda fue marginalmente más rápida.

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


 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 (menor es mejor):

encadenado 1.50960231881
aritmética 1.69729960569

En Python, hay una manera 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 recursión (como el error de StackOverflow en Java)

Respondí al problema de Euler usando un método 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 fue manejado por Begler tenía un enfoque tan novedoso, que decidí reimplementar mi solución usando su algoritmo. Su versión estaba en Python (usando bucles nesteds) y la reimplementé en Clojure (usando un solo bucle / recurrencia).

Aquí para su 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 (* ij)] (if (and (> product mx) (palindrome? (str product))) (recur product ij (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 no me las podían arreglar.

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

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

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 (ht) (cond ((< ht) #f) ((= ht) #t) (else (let* ((h2 (quotient h base)) (m (- h (* h2 base)))) (cond ((= h2 t) #t) (else (Q h2 (+ (* base t) m)))))))))) (Q n 0))))))) 

La forma más rápida que conozco:

 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; } 

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 } 

Solución recursiva en ruby, sin convertir el número en 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) 

Destape los primeros y últimos dígitos 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 reventados 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 palindrómicas insensibles a mayúsculas y minúsculas.

 template  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í está la versión af:

 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 entero y lo almacenan en una variable que usa espacio extra que es 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 compacidad.

 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 stacks 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 

Al abrir la stack solo se considera el lado derecho del número para comparar y falla rápidamente para reducir los controles

  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; } 

Manera 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)