No. 23 - Palindrome Numbers

Problem: Please implement a function which checks whether a number is a palindrome or not. For example, 121 is a palindrome, while 123 is not.

Analysis: Many candidates can get a straight solution which converts the input number into a string first. However, it is not what interviewers expect usually.

Solution 1: Convert a Number into a String

It is easy to check whether a number is palindrome or not: We can check whether the first character and the last one are identical, and then check the second character and the second one from end, and so on. Therefore, we can firstly convert the input number into a string via the function sprintf, and then check whether the string is a palindrome.

This solution can be implemented as the following code:

bool IsPalindrome_solution1(unsigned int number)

{

    const int NUMBER_LENGTH = 20;

    char string[NUMBER_LENGTH];

    sprintf(string, "%d", number);

    return IsPalindrome(string);

}

bool IsPalindrome(const char* const string)

{

    bool palindrome = true;

    if(string != NULL)

    {

        int length = strlen(string);

        int half = length >> 1;

        for(int i = 0; i < half; ++ i)

        {

            if(string[i] != string[length - 1 - i])

            {

                palindrome = false;

                break;

            }

        }

    }

    return palindrome;

}

Usually the solution above is not the one expected by interviewers. One reason is that it is intuitive while interviewers expect something innovative, and the other is that it requires auxiliary memory to store the converted string.

Solution 2: Compose a Reversed Number

As we know, it is easy to get digits from right to left via / and % operators. For example, digits in the number 123 are 3, 2 and 1. We can construct a reversed number 321 with these three digits. And then we check whether the reverse number is identical to the original one. If it is, the original number is a palindrome.

Its corresponding code is shown below:

bool IsPalindrome_solution2(unsigned int number)

{

    int reversed = 0;

    int copy = number;

    while(number != 0)

    {

        reversed = reversed * 10 + number % 10;

        number /= 10;

    }

    return (reversed == copy);

}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.