# 9. Palindrome Number

Reference: LeetCode EPI 4.9
Difficulty: Easy

## Problem

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

Note:

Example:

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

Hint: Beware of overflow when you reverse the integer.

## Analysis

Methods:

1. 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.
2. 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)$
3. 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.
• Time: $O(N) = O(\log_{10}{n})$ 7 ms
• Space: $O(1)$
4. 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)$

## Code

Test Case:

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

### 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$.

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

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

Comment
Junhao Wang
a software engineering cat