Saturday, August 3, 2013

How do I check if a number is a palindrome?

Note:
First, the problem statement did not specify if negative integers qualify as palindromes. Does negative integer such as -1 qualify as a palindrome? Finding out the full requirements of a problem before coding is what every programmer must do. For the purpose of discussion here, we define negative integers as non-palindromes.

Approaches to solve the problem

Approach 1:
The most intuitive approach is to first represent the integer as a string, since it is more convenient to manipulate.

Approach 2:
Reversing the number and checking if it is same, then it is palindrome as well.


int reverse(int num) {
  assert(num >= 0);   // for non-negative integers only.
  int rev = 0;
  while (num != 0) {
    rev = rev * 10 + num % 10;
    num /= 10;
  }
  return rev;
}

Now write isPalindrome(int number) method to see if the number is palindrome:
int isPalindrome(int orig)
{
  int reversed = 0, n = orig;
  reversed = reverse(orig);
/*
  while (n > 0)
  {
    reversed = reversed * 10 + n % 10;
    n /= 10;
  }*/

  return orig == reversed;
}

This is better in only step, that you don't have to convert to string. 

Approach 3 : Recursion
bool isPalindrome(int x, int &y) {
  if (x < 0) return false;
  if (x == 0) return true;
  if (isPalindrome(x/10, y) && (x%10 == y%10)) {
    y /= 10;
    return true;
  } else {
    return false;
  }
}
bool isPalindrome(int x) {
  return isPalindrome(x, x);
}

Reactions:

1 comment: