algorithm - numeros - palindromo en java

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

Question

¿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).

Answer 1

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

Answer 2

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

Answer 3

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 pila solo se considera el lado derecho del número para comparar y falla rápidamente para reducir los controles

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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

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

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

Answer 8

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.

Answer 9

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

Answer 10

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) 

Answer 11

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

Answer 12

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.

Answer 13

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;

Answer 14

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

Answer 15

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

Answer 16

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

Answer 17

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 anidados) 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 (* 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 no me las podían arreglar.

Answer 18

Siempre uso esta solución de python debido a su compacidad.

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

Answer 19

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;

Answer 20

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)

Answer 21

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

Answer 22

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
}

Answer 23

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

Answer 24

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

Answer 25

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

Answer 26

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

Answer 27

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.

Answer 28

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."

Answer 29

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

Answer 30

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)