My solution(C++) in O(n) time complexity and without extra space


  • 0
    A

    Here's my solution:
    calculate the reverse number of x, then compare whether x and reverse is the same
    Because a palindrome number will be same between original and reverse number.

        bool isPalindrome(int x) {
        if(x < 0)   return false;//assume negative number isn't a palindrome
        
        //calculate the reverse number of x, then compare whether x and reverse is the same
        //because a palindrome number will be same between original and reverse number.
        int reverse = 0, tmp = x;
        while(tmp != 0){
            reverse *= 10;
            reverse += (tmp % 10);
            tmp /= 10;
        }
        if(reverse == x)
            return true;
        return false;
    }

  • 0
    H

    Shorter version

        bool isPalindrome(int x) {
            int reverse = 0;
            for (int tmp = x; tmp != 0; tmp/=10)
                reverse += (reverse*9 + tmp % 10);
            return reverse == x && x>=0;
        }

  • 0
    B

    Hi! Can you please explain why is this O(log n) ? I would think that you are traversing the entire length of integer.. so it should be O(n)..


  • 0
    A

    Yes, I think you are right.
    I just made a mistake.
    Thank you for reminding me.


  • 0
    L

    I think it should be O(log(n)), since every time you divide tmp by 10. So finally, the loop just goes log10(n) times, where the time complexity should be O(log(n)).

    If every time we update the tmp by tmp--, this should yield the O(n) time complexity.

    Please correct me if I am missing something. Thanks!


  • 0

    I think my solution is better, is in O(log(n)) time complexity and without extra space!

    class Solution
    {
    public:
        bool isPalindrome(int x)
        {
    		if (x < 0)
    		{
    			return false;
    		}
            int bits = int(std::log10(double(x))), pow10 = 0;
            for (int i = 0; i <= bits; i += 2)
            {
    			pow10 = int(std::pow(double(10), bits - i));
                if (x / pow10 != x % 10)
                {
                    return false;
                }
                x = x % pow10 / 10;
            }
            return true;
        }
    };

  • 0

    Oh, I found my solution is also in o(n) time, I am very sorry!


  • 0
    P

    Why not multiply 10 instead of 9 in this line?
    reverse += (reverse*9 + tmp % 10);


  • 0
    Y

    he was using += operator. It has added one copy


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.