Table of contents
No headings in the article.
Hello everyone. Today we are going to solve the problem Palindrome Number. There are many way to do but first of all let look at the problem statement.
Given an integer x, return true if x is a palindrome, and false otherwise.
The examples input and output are below.
Example 1:
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.
Example 2:
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a Palindrome.
Constraints:
-2^31 <= x <= 2^31 - 1
The first idea that come in my mind is convert Integer to String then using two pointers technique to check from first index is equal to last index, second index is equal to previous last index, and so on. Then we will solve this problem by time complexity O(n). There also has some cost from creating String from Integer as well. However, look at bottom of the problem statement it said
Follow up: Could you solve it without converting the integer to a string?
So, we have to find another approaches.
[1] Brute Force This way is quite similar to convert Integer to String then reverse it. We have to reverse the Integer then check the reversed is equal to original. If yes, the Integer is Palindrome. We could start by thinking about edge cases that may happen during reverse the Integer. The first edge case is negative because if we try to revert negative it will be ended up with something invalid. For example
-123454321 => 123454321- // It' invalid so that it's not Parindome.
The second edge case is we have to be careful about overflow when reverse Integer. Since the maximum Integer is 2147483647 (In JAVA). If we revert that Integer it will be overflow Integer which is also invalid Palindrome as well.
2147483647 => 7463847412 // Overflow so that it's not Palindrome.
So we could start by checking the above edge cases. The code is below
if (x < 0 || x == Integer.MAX_VALUE) {
return false; // Return false immediately if edge cases are happened.
}
After that, we have to find how many digits for the Integer. We will use this value again later for Mathematic calculation.
int copyX = x;
int digit = 0;
while (copyX != 0) {
copyX /= 10;
digit++;
}
The next step is we just reverse the Integer by using divider (/) and modulo (%) operations. We also update the value of copyX and digit as well. This technique will pick the last digit one by one until copyX is equal to 0 which is end our loop. Then the rest of our job is just compare reversed Integer and original Integer. If they are the same, it's Palindrome.
int reversed = 0;
copyX = x;
while (copyX != 0) {
reversed += (copyX % 10) * Math.pow(10, digit - 1);
copyX /= 10;
digit--;
}
return reversed == x;
The full JAVA code is below
public boolean isPalindrome(int x) {
if (x < 0 || x == Integer.MAX_VALUE) {
return false;
}
int reversed = 0;
int copyX = x;
int digit = 0;
while (copyX != 0) {
copyX /= 10;
digit++;
}
copyX = x;
while (copyX != 0) {
reversed += (copyX % 10) * Math.pow(10, digit -1);
copyX /= 10;
digit--;
}
return reversed == x;
}
// Time complexity: O(n) or maybe O(1) see the description below.
// Space complexity: O(1)
Since we loop one by one digit so time complexity is O(n) where n is number of digits for the original Integer. However, we could say it's O(1) as well because we are limiting input by number of digit for Integer.MAX_VALUE. The space complexity is O(1) because we just use some variables to store values regardless of the input.
This solution is working well but we have to loop twice and also the calculation is looking confusing as well (at least for me). Let see next solution together.
[2] Reverse half-Integer what if we just reverse half of Integer then compare the 1st part and 2nd part. If they are the same, it's Palindrome. Let start by looking at the example of valid Palindrome Integer.
12344321 => [1234][reverse of 4321] => 1234 == 1234 => Palindrome
34543 => [34][5][reverse of 43] => 34 == 34 => Palindrome // The middle digit could be ignore. It does not matter if left part is still equal to right part.
The reversed half-Integer code (Swift) is below.
func isPalindrome(_ x: Int) -> Bool {
// Checking edge cases. Negative case and the case that ending with 0 will be Palindrome only if it is 0.
if x < 0 || (x % 10 == 0 && x != 0) {
return false
}
var x = x
var reversed = 0
while x > reversed { // We know that we have reached the middle digit by checking value of `x` and `reversed`
reversed = reversed * 10 + (x % 10)
x /= 10
}
return reversed == x || x == reversed / 10 // Ignore the middle digit if it's odd digits.
}
// Time complexity is O(log n)
// Space complexity is O(1)
The second approach has time complexity O(log n) because We divided the input by 10 for every iteration.
Thank you for your time. If you enjoy my sharing daily problem solving solution feel free to comment, like, subscribe and share so the others could get benefit from this. See you again later. ʕ•ᴥ•ʔ