Make the frequent cases fast and the rare case correct

Algorithm to check if a number is Palindrome

This is a standard question in computer science, extended to Strings as well.

There are numerous ways to accomplish this. In this article i will show you a recursive procedure. This article will be updated in future with implementation of several approaches, for now this article is a preface to some articles that i will be writing and i felt i need to get this basic palindrome question before diving into some other concepts in number theory.

Algorithm in the code is self explanatory

int pal=0; 
int Palindrome(int num)
 		pal=(pal*10)+ (num %10);
 		Palindrome(num / 10); //recursion.        
	return pal;       
int main()
	int num;
	printf("Enter a number \n");
	printf("Number is a Palindrome\n");	
	printf("Not a palindrome\n");
	return 0;   

laptop:~/code$ ./a.out
Enter a number
Not a palindrome

laptop:~/code$ ./a.out
Enter a number
Number is a Palindrome

Also in future i will talk about palindrome implementation with Linked Lists.

Watch this space !

2 responses to “Algorithm to check if a number is Palindrome

  1. bartender February 13, 2013 at 12:48 pm

    Algorithm Explanation:

    The Palindrome function reverses the number and checks if it’s equal to the original number.

    We keep extracting digits from the back/tail of the number using % with 10 which gives the last digit of the remaining number.We multiply the existing value of pal by 10 and add the extracted digit to the pal value,so that we can revert the whole number step by step.

    example if at some point pal = 34, and last extracted digit =7,we basically want to convert pal = 347 from existing 34, so we multiply it by 10 and it becomes 340 ,i.e. digit at units place gets shifted to hundreds and the one at hundreds place to thousands etc., and the new units place becomes 0,then we add the last extracted digit to the 340 i.e. 340+7= 347.
    So, during this whole process,in the end the number will be reverted.

    Example if we pass 76543 to the palindrome function. here is what happens:

    pal = 0 + 3 = 3; val =7654 (0 is the value of global pal initially and 3 is 34543%10)
    pal = 3*10 + 4 = 34; val =765
    pal = 34*10 +5 = 345; val = 76
    pal = 345*10 + 6 = 3456; val = 7
    pal = 3456*10 + 7 = 34567 ( i.e. 76543 in reverse order) val=0 (recursion ends)

    this value 34567!= 76543 so, 76543 is not a palindrome.

  2. rj007 April 7, 2013 at 7:06 am

    There is a possibility that the reversed number might overflow for size of an INT. If it overflows, the behavior is language specific. For Java the number wraps around on overflow, but in C/C++ its behavior is undefined. Hence better will be to do it without storing reverse number in any variable, just work with left most and right most digit at a time:

    bool isPalindrome(int x) {
    if (x = 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;

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: