Palindrome Number


  • 0
    C

    Click here to see the full article post


  • 0
    B

    How would you handle such case if the length of an integer is odd?


  • 1
    C

    @baichuan0898 It's explained in the code:

            // When the length is an odd number, we can get rid of the middle digit by revertedNumber/10
            // For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123, 
            // since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
            return x == revertedNumber || x == revertedNumber/10;
    

  • 0
    K

    Do we have to avoid the integer overflow problem? reversing a palindromic integer will not overflow, and if the reversed integer overflows, the overflown result will not be equal to the original, the original number is not a palindrome.

    Nevertheless, you approach is a very nice idea!


  • 0
    C

    @kamfung2017 it's best if there's no integer overflow during the algorithm calculation. In many languages overflow behaviors are not defined. Although unlikely, who knows if it happens that some non-palindrome number, after the overflow during the 'reverse' process, happen to equal to the original number :)?


  • 0
    C

    constant 0 is extra space, your algorithm is not met with the requirement of the problem,"no extra space"


  • 0
    C

    Can't we do this ->

    given a number, find its digit length by taking log(n) [base 10] then running a loop exactly half this number to check if n%(pow(10, i)) == n%(pow(10, n-i)) ?


  • 0
    C

    Okay I realize my method is flawed. Your approach is correct, cheers !


  • 0
    K

    Man, python makes this super easy:

    class Solution(object):
        def isPalindrome(self, x):
            return str(x) == str(x)[::-1]
    

  • 1
    T

    I agree with codingcrazer "no extra space" is not the same as O(1) space. The question should be re-written to say constant space. I assert (without proof) that the original question is impossible.

    PS kasshmonee - your algorithm is O(n) space due to conversion to string.


  • 0
    B

    @ccwei I got it. Thank you for your reply : )


  • 0
    K

    @thermite Oh I see, this can take a long time for very long strings...


  • 0
    Z

    @thermite You are 100% correct.


  • 0
    Y

    if the number is not overflow while the reversed number is overflow, it cannot be the palindrome...


  • 0
    S

    @kaashmonee Great one line solution. However, if I'm not mistaken doesn't creating the str(x) and then recreating the inverse of using [::-1] use O(n) space, instead of O(1)?


  • 0
    E

    3-line accepted Python code
    class Solution(object):
    def isPalindrome(self, x):
    return str(x)==str(x)[::-1] if x>0 else False


  • 0
    C

  • 0
    D

    Accepted JAVA code using mathematical operations:

    class Solution {
    public boolean isPalindrome(int x) {
    //handle negative integers
    if(x<0)
    return false;
    //get the divisor for x
    int div = 1;
    while(x/div >= 10)
    div = div*10;

        //check first and last digits if they are same
        while(x > 0){
            if(x%10 != x/div)
                return false;
            
            x = (x%div)/10;
            div = div/100;
        }      
        return true;
    }
    

    }

    Time complexity: O(logn)
    Space complexity: O(1)


  • 0

    above code is not returning false for 2145412.


  • 0

    I am sorry, I meant above code is returning false for isPalindrome(2145412) which is a palindrome.


Log in to reply
 

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