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

• ``````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.

• good ending condition to avoid overflow

• Beautiful code, thank you very much!

• 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!

• 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.

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

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

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

• 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 .

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

• I think you are right.

• yeah,I agree that

• I think evlstyle is right!

• I think your p and q use extra spaces?

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

• @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.

• @evlstyle

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

• 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);
}
}
``````

• @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
``````

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