Saturday, November 26, 2011

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. 

2 comments:

  1. you don't have to reverse the entire number
    you can just reverse half of it and then compare to the half that is left

    public static boolean isPalindrom(int n) {
    int newNumber = 0;

    while (newNumber < n) {
    newNumber *= 10;
    newNumber += n % 10;

    if (newNumber == n) {
    break;
    }

    n /= 10;
    }

    return (newNumber == n);
    }

    ReplyDelete
  2. I don't follow it, because you are constantly, multiplying reverse * 10, so depending on the number of times you loop, it will be several orders of magnitude larger than copy....

    //132
    reversed = reversed * 10 + number % 10;
    //#1
    reversed = 1320 + y0
    //#2
    reversed = 132x0 + y1
    etc..

    ReplyDelete