# [data structure and algorithm] in-depth analysis of the solution idea and algorithm example of "palindrome number"

## 1, Title Requirements

• Give you an integer X. if x is a palindrome integer, return true; Otherwise, false is returned.
• Palindromes are integers that are read in the same positive order (from left to right) and reverse order (from right to left). For example, 121 is palindrome, not 123.
• Example 1:
```Input: x = 121
Output: true
```
• Example 2:
```Input: x = -121
Output: false
Explanation: read from left to right, by -121 .  Read right to left, Is 121- . Therefore, it is not a palindrome number.
```
• Example 3:
```Input: x = 10
Output: false
Explanation: read from right to left, Is 01. Therefore, it is not a palindrome number.
```
• Example 4:
```Input: x = -101
Output: false
```
• Tip: - 231 < = x < = 231 - 1.

## 2, Solving algorithm

### ① Integer to string

• The best solution is to convert an integer into a string, and then divide the string into arrays. You only need to cycle half the length of the array to judge whether the corresponding elements are equal:

• Java example:
```class Solution {
public boolean isPalindrome(int x) {
String reversedStr = (new StringBuilder(x + "")).reverse().toString();
return (x + "").equals(reversedStr);
}
}
```

### ② Mathematical solution

• Obtain the corresponding number in the integer through rounding and remainder operations for comparison.
• For example, the number 1221:
• By calculating 1221 / 1000, the first 1 is obtained;
• By calculating 1221% 10, the last 1 can be obtained;
• Compare;
• Then take out 22 and continue to compare.

• Java example:
```class Solution {
public boolean isPalindrome(int x) {
if (x < 0) return false;
int div = 1;
while (x / div >= 10) div *= 10;
while (x > 0) {
int left = x / div;
int right = x % 10;
if (left != right) return false;
x = (x % div) / 10;
div /= 100;
}
return true;
}
}
```

### ③ Take out the second half of the number and flip it

• If you look at the palindrome number intuitively, it feels like folding the numbers in half to see whether they can correspond one by one. Therefore, the operation of this solution is to take out the second half of the numbers and flip them.
• One thing to note here is that the number of palindromes can be odd or even, so when its length is even, it should be equal when folded in half; When its length is an odd number, after it is folded in half, one digit of its length needs to be removed (divided by 10 and rounded).
• The specific methods are as follows:
• Take out the lowest number for each remainder operation (% 10): y = x% 10;
• Add the lowest number to the end of the fetched number: revertNum = revertNum * 10 + y;
• For each lowest digit, x must be divided by 10;
• Judge whether x is less than revertNum. When it is less than, it indicates that the number has been halved or more than half;
• Finally, judge the case of odd and even numbers: if it is even, revertNum and x are equal; If it is an odd number, the middle number is on the lowest bit of revertNum. After dividing it by 10, it should be equal to x.

• Java example:
```class Solution {
public boolean isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
return x == revertedNumber || x == revertedNumber / 10;
}
}
```

### ④ Reverse half number (LeetCode official solution)

• The first idea that comes to mind is to convert numbers into strings and check whether the strings are palindromes. However, this requires additional non constant space to create strings that are not allowed in the problem description.
• The second idea is to reverse the number itself, and then compare the reversed number with the original number. If they are the same, then this number is a palindrome.
• However, if the inverted number is greater than int.MAX, an integer overflow problem will be encountered.
• According to the second idea, in order to avoid the overflow problem caused by number inversion, why not consider inverting only half of the int number? After all, if the number is a palindrome, the second half should be the same as the first half of the original number after inversion. For example, by entering 1221, we can reverse the second half of the number "1221" from "21" to "12" and compare it with the first half of "12", because they are the same, we know that the number 1221 is a palindrome.
• First, some critical situations should be addressed. All negative numbers cannot be palindromes. For example: - 123 is not a palindrome. Because - is not equal to 3, false can be returned for all negative numbers. Except 0, all numbers with 0 bits cannot be palindromes. Because the highest bit is not equal to 0, false can be returned for all numbers greater than 0 and 0 bits.
• Now, let's consider how to reverse the second half of the number: for number 1221, if we execute 1221% 10, we will get the last digit 1. To get the penultimate digit, we can first remove the last digit from 1221 by dividing by 10, 1221 / 10 = 122, and then find the remainder of the result of the previous step divided by 10, 122% 10 = 2, You can get the penultimate number. If we multiply the last digit by 10 and add the penultimate digit, 1 * 10 + 2 = 12, we get the inverted digit we want. If we continue this process, we will get more reversed digits.
• The question now is, how do we know that the number of digits of the inverted number has reached half of the number of digits of the original number? Since we continue to divide the original number by 10 and multiply the inverted number by 10, when the original number is less than or equal to the inverted number, it means that we have processed half digit numbers.

• Java example:
```class Solution {
public boolean isPalindrome(int x) {
// exceptional case:
// As mentioned above, when x < 0, X is not a palindrome number.
// Similarly, if the last digit of the number is 0, in order to make the number palindrome,
// Then its first digit should also be 0
// Only 0 satisfies this property
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}

int revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}

// When the number length is odd, we can remove the number in the middle by revertedNumber/10.
// For example, when the input is 12321, we can get x = 12, revertedNumber = 123 at the end of the while loop,
// Since the median number does not affect the palindrome (it is always equal to itself), we can simply remove it.
return x == revertedNumber || x == revertedNumber / 10;
}
}
```

Keywords: data structure leetcode

Added by renojim on Thu, 13 Jan 2022 19:44:26 +0200