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


  • 0

    Each time, comparing numerical value of the highest and lowest.

    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
    Q

    I don't understand why there is no extra space.
    You have int bits, pow10, and int i.
    They are all extra memory spaces.


Log in to reply
 

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