How do I check if a number is a palindrome?

Question

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

Also, I actually have to do this, and I'll be posting my solution too.

Answer 1

This is one of the Project Euler problems. When I solved it in Haskell I did exactly what you suggest, convert the number to a String. It's then trivial to check that the string is a pallindrome. If it performs well enough, then why bother making it more complex? Being a pallindrome is a lexical property rather than a mathematical one.

Answer 2

Push each individual digit onto a stack, then pop them off. If it's the same forwards and back, it's a palindrome.

Answer 3

For any given num:

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

If n == rev then num is a palindrome:

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

Answer 4

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

Answer 5

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 6

Pop off the first and last digits and compare them until you run out. There may be a digit left, or not, but either way, if all the popped off digits match, it is a palindrome.

Answer 7

I would be very interested to see an algorithm that is not equivalent -- modulo the +/- 48 needed to convert between ASCII digits and ints -- to converting to a string and reversing.

---

Edit: I should have read the other answers more carefully before I posted. smink's converts the stream of digits into the reversed number without just reversing the digits.

Answer 8

I answered the Euler problem using a very brute-forcy way. Naturally, there was a much smarter algorithm at display when I got to the new unlocked associated forum thread. Namely, a member who went by the handle Begoner had such a novel approach, that I decided to reimplement my solution using his algorithm. His version was in Python (using nested loops) and I reimplemented it in Clojure (using a single loop/recur).

Here for your amusement:

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

There were Common Lisp answers as well, but they were ungrokable to me.

Answer 9

Just for fun, this one also works.

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 10

Here is an Scheme version that constructs a function that will work against any base. It has a redundancy check: return false quickly if the number is a multiple of the base (ends in 0). And it doesn't rebuild the entire reversed number, only half. That's all we need.

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