How do I check if a number is a palindrome?

Question

How do I check if a number is a palindrome?

Any language. Any algorithm. (except the algorithm of making the number a string and then reversing the string).

Answer 1

Here is one more solution in c++ using templates . This solution will work for case insensitive palindrome string comparison .

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 2

except making the number a string and then reversing the string.

Why dismiss that solution? It's easy to implement and readable. If you were asked with no computer at hand whether 2**10-23 is a decimal palindrome, you'd surely test it by writing it out in decimal.

In Python at least, the slogan 'string operations are slower than arithmetic' is actually false. I compared Smink's arithmetical algorithm to simple string reversal int(str(i)[::-1]). There was no significant difference in speed - it happened string reversal was marginally faster.

In low level languages (C/C++) the slogan might hold, but one risks overflow errors with large numbers.

---

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)

Results in seconds (lower is better):

strung 1.50960231881
arithmetic 1.69729960569

Answer 3

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 4

Recursive solution in ruby, without converting the number to string

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 5

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 6

Fastest way I know:

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