## 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);
}
```