Reference: LeetCode EPI 4.9

Difficulty: Easy

My Post: Four Solutions All In One (Why overflow is a problem?)

## Problem

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

**Note:**

**Example:**

1 | Input: 121, 0, 100, -120 |

**Follow up:** Could you solve it without converting the integer to a string?

**Hint:** Beware of `overflow`

when you reverse the integer.

## Analysis

**Methods:**

- Brute-Force
- Convert the number to a string.
**Time:**$O(N)$, where $N$ is the number of characters.`8 ms`

**Space:**$O(N)$, since we create a string.

- ReverseAndCompare
- Reverse a number and compare it to the initial one.
- Note: Be aware of overflow problem.
**Time:**$O(N)$`6 ms`

**Space:**$O(1)$

- Reverse Half
- Similar idea to ReverseAndCompare, but it only reverts half of the
`int`

number. If the reverse of the last half of the palindrome should be the same as the first half.- E.g.
`1221`

from`21`

to`12`

.

- E.g.
**Time:**$O(N) = O(\log_{10}{n})$`7 ms`

**Space:**$O(1)$

- Similar idea to ReverseAndCompare, but it only reverts half of the
- CompareOneByOne EPI 4.9
- Calculate the most significant digit
`msd`

and the least significant digit`lsd`

and compare. `numDigit`

=`(int) Math.floor(Math.log10(x)) + 1`

**Time:**$O(N)$`8 ms`

**Space:**$O(1)$

- Calculate the most significant digit

## Code

**Test Case:**

1 | Input: 121, 0, 100, -120 |

### Brute-Force

**Note:**

- The condition could be written as:
`if (x <= 0) return x == 0`

- Since the code can handle $0$ case, it is fine.

- Be careful of the corner case
`n / 2`

- When getting the size of a String, remember to use
`str.length()`

rather than`str.length`

.

1 | // convert to string |

### ReverseAndCompare

**Note:**

- Be aware of potential overflow problems.
- It’s doomed when the reversed number of $x$ overflows. Marked
- But it seems okay because I can’t input number larger than
`2147483647`

. - Also, if
`x`

is`2147483647`

, the reversed number is`7463847412`

which is actually a negative number that could not be equal to $x$.

- But it seems okay because I can’t input number larger than

1 | // reverseAndCompare |

### Reverse Half

**Note:**

- Careful of the corner case. Test it out for
`x = 0`

and`x = 100`

. Unlike other solutions, this one requires special check for those numbers. - In the return statement, there are different cases for even or odd numbers.

1 | // revert half |

### CompareOneByOne

**Note:**

- Learn how to calculate the number of digits.
- Use
`msdMask`

to get the most significant digit. - Can use
`while`

or`for`

, but`for`

turns out to be clearer.

1 | // compareOneByOne |