Algorithm and Sample C Code to Check if a Number is a Palindrome – Without Reversing the Digits

A friend posted this question on my college mailing list.

How do we find if a Number is a Palindrome?

Note: No conversion to string. And also, no traditional method of dividing the number to construct the reversed number and then compare.

Here is how you go about it.

  1. Lets say the number is 1987891 (odd number of digits)
  2. Reduce it to 198891. If the number were 19877891 (even number of digits) don’t change it (basically change it to a number with even number of digits, by excluding the middle digit)
  3. Now Split it into 198 and 891
  4. If ((891-198)%9 == 0 and (891*1000+198)%11 == 0 and (198*1000+891)%11 == 0) then its a palindrome

Sample C Code

#include <stdio.h>

int numdigits(int n) {
    int count = 0;
    while(n != 0)   {
        n /= 10;
        ++count;
    }
    return count;
}

int main(void) {
    int n;
    int l;
    int a,x;
    int n1, n2, n3;
    scanf("%d",&n);
    l=numdigits(n);     /* Find the number of digits */
    a=1;
    for(x=0;x<l/2;x++)
        a*=10;
    n1=n%a;
    n2=n/a;
    if(l%2)
        n2/=10;
    if (((n1-n2)%9 == 0) && ((n2*a+n1)%11 == 0) && ((n1*a+n2)%11 == 0)) {
        printf("%d\t",n);
        return 0;
    }
    return 1;
}

To compile it

gcc -o palindrome palindrome.c

You can verify that above code works using the below script.

#!/bin/bash

for (( i = 0; i < 100000; i++ )); do
  echo $i | ./palindrome
done

The script assumes that the palindrome binary is in the present working directory.

Jotted this down for school students scouring the web for their homework answers: 😉

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.