LeetCode

LeetCode - Palindrome Number

2013.12.1 22:24

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Solution:

　　Basic solution for this problem is to compare the digits at both ends of the number one by one, until all pairs are determined equal.

　　Here are the special cases I've come up with:

　　　　1. 0 is of course a palindrome.

　　　　2. INT_MIN and INT_MAX, boundary values can be tricky.

　　　　3. negative numbers like -121?

　　Actually the first two case needs special treatment, as they won't work with the code below. The third case cost me 1WA to find out that -121 is not considered a palindrome by LeetCode OJ. For other numbers, the following code segment works just fine.

　　Time complexity is O(lg(n)), space complexity is O(1).

Accepted code:

// 1RE, 1WA, 1AC  must be more careful
class Solution {
public:
    bool isPalindrome(int x) {
        // 1RE here, ignored the case of INT_MIN
        if(x == INT_MAX || x == INT_MIN){
            return false;
        }
        
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int high, low;
        
        if(x < 0){
            // 1WA here, seems negative number is not palindrome, that's unfair..
            return false;
        }
        
        if(x == 0){
            return true;
        }
        
        high = low = 1;
        while(x / high >= 10){
            high *= 10;
        }
        
        while(high > low){
            if(x / high % 10 != x / low % 10){
                return false;
            }else{
                // fixed, didn't cause a WA, lucky..
                high /= 10;
                low *= 10;
            }
        }
        
        return true;
    }
};