## Summary

The negative number is not count for palindrome, so we always return `False`

.

## Approach #1 Divide by 10 [Accepted]

**Concept**

We divide x by 10 to get remainder so that we can form the reverse of x.

But we may encounter overflow problem.

**Algorithm**

- check whether
`x`

is negative or`x`

is digit in ones - let
`reverse`

be 0 and`remain`

be`x`

- if
`remain`

is greater than or equal to 10- shift
`reverse`

left for propagation - cut the right most digit in
`remain`

to give to`reverse`

- shift
`remain`

right for dropping zero digit

- shift
- compare
`reverse`

with x which is not including right most digit

**Python**

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

**Complexity Analysis**

- Time complexity : $$O(log_10 n)$$.

We divide n by 10 each time, so we have a equation: $$\frac{n}{10^{x}} = 1$$

Multiply both sides by $$10^{x}$$

$$n = 10^{x}$$

- Space complexity : $$O(1)$$.

Only 2 variables for constant memory space.

## Approach #2 Comparing in string type [Accpeted]

**Concept**

- To avoid overflow problem, we take the way of converting number to string.
- We convert
`x`

into string type, so that we can access it with index like`array`

. - But it needs extra memory space for string type of
`x`

.

**Algorithm**

- we only need to check half index so we range from 0 to half number of digits.
- we access it with index, and compare it with the corresponding digits.

**Python**

```
class Solution(object):
def isPalindrome(x):
"""
:type x: int
:rtype: bool
"""
if x < 0:
return False
if x / 10 == 0:
return True
x = str(x)
n = len(x)
for i in range(int(n/2)):
if x[i] != x[n-i-1]:
return False
return True
```

**Complexity Analysis**

- Time complexity : $$O(n)$$.

Even we only take half number of digits, the time complexity is O(n/2) = O(n).

- Space complexity : $$O(len(x)) = O(n)$$.

We need extra memory space for string type of x.

## Approach #3 Revert half of digits [Accpeted]

**Concept**

If we have to consider about overflow and no extra constant memory space, we can compare only half number without using string type.

This is also an improved approach #1, we use better `while`

loop condition to decrease computing times.

The key idea is that we mutate `x`

and compare it with `reverse`

, and we can reach half number of digits when `x <= reverse`

.

Note that we need to add a `return`

case for even number of digits.

E.g. Asuumed `x = 11`

, we exit `while`

loop when `x = 1`

and `reverse = 1`

(`x`

is not greater than `reverse`

), so we have to ensure `x == reverse`

.

**Algorithm**

- initialize
`reverse`

to 0 - we set up
`while`

condition for`exit when x <= reverse`

- In
`while`

loop:- propagate for
`reverse`

- add right most number in
`x`

to`reverse`

- shift
`x`

to left for 1 digit

- propagate for
- return both cases for odd and even number of digits

**Python**

```
class Solution(object):
def isPalindrome(x):
"""
:type x: int
:rtype: bool
"""
reverse = 0
while x > reverse:
reverse = reverse * 10
reverse += x % 10
x = int(x / 10)
return x == reverse or x == int(reverse / 10)
```

**Complexity Analysis**

- Time complexity : $$O(n)$$.

We only compare digits for n/2 times, so the time complexity is $$O(n)$$

- Space complexity : $$O(1)$$.