[LeetCode Road] Palindrome Number - Solution/C++

9. Palindrome Number

Question:

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Follow up: Could you solve it without converting the integer to a string?

Example:

Input: x = 121
Output: true

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Input: x = -101
Output: false

Constraints:

-2^31 <=x <= 2^31 -1

Source code

Version 1

Idea:
My solution is the same as "Reverse Integer". Use the reverse integer to compare with the original value, so you can get the result.

class Solution {
public:
    bool isPalindrome(int x) {
        long ans = 0, temp = x;
        if(x >= 0){
            while(x){
                ans = ans * 10 + x % 10;
                x = x / 10;
            }
            if(temp == ans){
                return (ans > INT_MAX)?0:true;
            }
        }      
        return false;
    }
};

Version 2

Idea:
The solution is refered from online. At if statement, it filters negative numbers and multiples of 10. while(x >sum) means cutting x in half. If x is even digits, use sum == x to get answer, on the contrary, use sume / 10 == x. This method of computing time is fater than Version 1 if x is a large number.

Time complexity: O(floor(log(10)(x))/2+1)
Space complexity: O(1)

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)){
            return false;
        }
        int sum = 0;
        while(x > sum){
            sum = sum * 10 + x % 10;
            x = x / 10;
        }      
        return (sum == x)||(sum / 10 == x);
    }
};