LeetCode 9. Palindrome Number

[English ver]

9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.


click to show spoilers.

Some hints:
Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.


Approach 1 Revert the number:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isPalindrome(int x) {
if (x < 0||(x % 10 == 0 && x != 0)) return false;
//use to calculate the number we used to revert the number ,and the biggest digit
int temp = x;
//the number reverted
int revertedNumber = 0;
while (temp >= 10){
revertedNumber *=10;
revertedNumber += temp%10;
temp /=10;
}
//compare the revertedNumber and x/10,and the temp and x%10.because the case of overflows
return revertedNumber == x / 10 && temp == x % 10;
}

Efficiency

Analysis
Because of the case overflows ,so revert the whole x except the largest digit , and then compare reverted Number with x which except the smallest digit , at last campare the biggest digit and the smallest digit.

Time complexity : O($log{_10}n$)
Space complexity : O(1) .

Approach 2 Revert half of the number:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public boolean isPalindrome(int x) {
// Special cases:
// As discussed above, when x < 0, x is not a palindrome.
// Also if the last digit of the number is 0, in order to be a palindrome,
// the first digit of the number also needs to be 0.
// Only 0 satisfy 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 length is an odd number, we can get rid of the middle digit by revertedNumber/10
// For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,
// since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.
return x == revertedNumber || x == revertedNumber/10;
}
}

Efficiency

Analysis

First of all we should take care of some edge cases. All negative numbers are not palindrome, and number x which x % 10 == 0 && x != 0 can not be palindrome ,because the number can’t be both 0 in the first digit and last digit. Then we start to convert number , we can use x%10 to get the last digit of x , update x to x/10 ,it remove the last digit ,and then use x%10 to get the last number of x , use the number we have get before to times 10 plus this number. Continuing this process would give us the reverted number with more digits. when the original number is less than the reversed number, it means we’ve processed half of the number digits.

Because palindrome has odd and even ,so we need to deal with both of them.When the palindrome is odd the reverted number will have one more digit ,but this digit we don’t need to consider about ,we only need to remove this digit and compare the rest of it ,when palindrome is even ,if we convert the half of number x ,if they don’t equal to each other it is not a palindrome , even x is bigger than reverted number , which make it revert one more time , the reverted number will hava more two digit to x ,remove one digit will nerver make it palindrome.

Time complexity :O($log{_10}n$)
Space complexity : O(1) .

If you have any suggestions to make the logic and implementation more better , or you have some advice on my description. Please let me know!Thanks!

About Me

我的博客 leonchen1024.com

我的 GitHub https://github.com/LeonChen1024

微信公众号

wechat

You forgot to set the business and currency_code for Paypal. Please set it in _config.yml.
You forgot to set the url Patreon. Please set it in _config.yml.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×