O(1) space, O(lgn) time java solution, no overflow risk


  • 64
    E
    public boolean isPalindrome(int x) {
        
        if (x < 0) return false;
    
        int p = x; 
        int q = 0; 
        
        while (p >= 10){
            q *=10; 
            q += p%10; 
            p /=10; 
        }
        
        return q == x / 10 && p == x % 10;
    }
    

    // so the reversed version of int is always 1 time short in the factor of 10s .

    in case of Int16, check 63556 will finally check if (6553 == 6355 && 6 == 63556%10) so there will have no concerns about the overflow.


  • 0
    S

    good ending condition to avoid overflow


  • 0
    A

    Beautiful code, thank you very much!


  • 10
    W

    It seems you do not need to compare p == x % 10 in the end, cause it is already compared in q == x / 10.
    For example: if x=345543, in the end, p=34554 in which 3 comes from the last digit of x.

    Just a suggestion, it is really a nice solution!


  • 16
    C

    Good solution, but the time complexity seems to be O(n) because you are iterating through the whole length of x with that while loop.


  • 0
    E

    It's log n /log 10 so it's lgn


  • 0
    A

    great answer !


  • 0
    L

    you reverse half of the integer and then compare it.i think the time complexity is O(N).


  • 4
    L

    i agree with you that the time complexity is O(N).


  • 0
    E

    It is not. In the while loop each time the p is divided by 10 , so it takes log10 P time to finish up the loop. As I explained, it is lg P .


  • 0
    H

    Thank you for sharing your nice solution. But I think the time complexity is O(N).


  • 0
    P

    I think you are right.


  • 0
    E

    yeah,I agree that


  • 0
    M

    I think evlstyle is right!


  • 0

    I think your p and q use extra spaces?


  • 0
    G

    @evlstyle: Your solution is correct but your analysis is wrong and misleading. It should be O(N) where N is the number of digits.


  • 0
    P

    @GreenTea211 The complexity O(n) where n is the length - aka the number of digits IS EQUAL to O(lgn) where n is the number itself.


  • -2
    W

    @evlstyle

    There is no O(logN) solution for this question. Period. Your solution is really nice and it takes O(N).


  • 1
    T

    I this is my answer.
    I think i is twice as fast.
    If the input is 202202, it would compare 202 and 202.

    It currently runs for 200+ ms.
    Beats 19% of submission.

    Any idea how I can improve this?

    public class Solution {
        public boolean isPalindrome(int x) {
            if (x >= 0 && x < 10) {
                return true;
            }
            if (x < 0) {
                return false;
            }
            if (x % 10 == 0) {
                return false;
            }
            int r = 0;
            while(r < x) {
                int e = x % 10;
                x = x / 10;
                if (r == x) {
                    return true;
                }
                r = r * 10;
                r = r + e;
            }
            return (r == x);
        }
    }
    

  • 0
    Y

    @ttwd80
    I rewrite it using python such code like

    class Solution(object):
        def isPalindrome(self, x):
            """
            :type x: int
            :rtype: bool
            """
            if x < 0:
                return False
                
            if x / 10 == 0:
                return True 
            
            if x % 10 == 0:
                return False
          
            h = x
            l = 0
            while h > l:
                l *= 10
                l += h % 10
                if l == h:
                    return True
                h /= 10
            return h == l
    

    It takes 235ms and is faster than the flowing code which takes 269 ms

    class Solution(object):
        def isPalindrome(self, x):
            """
            :type x: int
            :rtype: bool
            """
            if x < 0:
                return False
            r = 0
            t = x
            while t:
                r *= 10
                r += t%10
                t = t/10
    
            return r == x
    

Log in to reply
 

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