Palindrome Number

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

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.

tag: math

9/25/2015 update

a neater approach

//negative can not be palindrome
class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        int len = 0;
        int y = x;
        while(y > 0){
            len++;
            y = y / 10;
        }
        while(x > 0){
            int highestDigit = x / pow(10, len - 1);
            int lowestDigit = x % 10;
            if(highestDigit != lowestDigit) return false;
            x -= highestDigit * pow(10, len - 1);
            x = x / 10;
            len -= 2;
        }
        return true;
    }
};

挺复杂的题，关键是不让用额外的空间。
版本一的想法是在每次循环中，把最高位和最低位的数字取出来，分别一次比较，但是！遇到1000021这样的情况就无法通过，因为当我把最高位1取掉后，直接变成了21，把零都忽略了，考虑改进中。

更新：

增加一个成员变量numOfZeros记录取掉数字的最高位后，露出的零的个数。这样当调用getHighestDisit函数时，先判断numOfZeros是否为0，如果大于零，则numOfZeros减1并返回0。在main函数中，当我发现取到的highestDigit不是0时，则更新numOfZeros的值。

class Solution {
public:
    int numOfZeros = 0;
    bool isPalindrome(int x) {
        int length;
        int leastDigit, highestDigit;
        
        if(x < 0){//negative integer can not be palindrome
            return false;
        }
        length = getNumLength(x);
        if (length == 1){
            return true;
        }
        
        while(x >= 10){
            leastDigit = x % 10;
            highestDigit = getHighestDigit(x);
            if (leastDigit != highestDigit){
                return false;
            }
            int length = getNumLength(x);
            x -= highestDigit * pow(10, length - 1);
            if(highestDigit != 0){
                numOfZeros = length - getNumLength(x) - 1;
            }
            x /= 10;
        }
        if(x > 0 && numOfZeros > 0){
            return false;
        }
        return true;
    }
    int getNumLength(int x){
        int i = 1;
        while(x / 10 > 0){
            x /= 10;
            i++;
        }
        return i;
    }
    int getHighestDigit(int x){
        int length = getNumLength(x);
        int i = 0;
        if(numOfZeros > 0){
            numOfZeros--;
            return 0;
        }
        while(x >= 0){
            x -= pow(10, length - 1);
            i++;
        }
        i--;
        return i;
    }
};