Palindrome Number - Leetcode #9 Short & Simple Solution
Updated: Jun 20, 2022
Problem Statement
In our previous article we solved the string to integer problem. This is another article in the series leetcode problem solutions and this article is a solution to leetcode 9 problem.
Given an integer x, return true if x is a palindrome integer. An integer is a palindrome when it reads the same backward as forward. Example, 121 is a palindrome while 123 is not.
Constraints:
-2^31 <= x <= 2^31 - 1
Example
Example 1
Input: x = 121
Output: trueExample 2
Input: x = -121
Output: falseExample 3
Input: x = 10
Output: falseSolution
This is one of the easier problems on leetcode and also an important one because the solution involves ingredients necessary to solve similar problems around number manipulation.
Lets understand the problem statement first. In this problem we are given an integer value as input, our task is to write an algorithm that tells us whether the given number is a palindrome or not. So, what are palindromic numbers? A number is a palindrome if it remains same when its digits are reversed. In other words a number is a palindrome if we get the same sequence of digits whether we read the number from left to right or right to left. For example 121, 99, 2332 etc. are palindromic numbers.
Solution 1
The first solution that might come to your mind when you look at this problem is to convert the given integer number to a string first, reverse it and then check if it is a palindrome or not as it is easier to reverse and compare individual characters in a string as compared to an integer. But converting an integer to a string is an extra overhead, is it possible to solve this problem by avoiding this extra overhead?
It turns out this problem can be efficiently solved using the divide and mod operations. The idea is to reverse the given number by applying the divide (/) and mod (%) operations on it and then compare the reversed number with original number to see if it is a palindrome. If both original and reversed numbers are equal, then the given number is a palindrome, otherwise it is not a palindrome.
To reverse the given number we need to do the following steps:
Get individual digits from the given number from right to left using the mod operator.
Put the digit obtained in step 1 into correct position in the reversed number.
Discard the currently processed digit from the original number.
Lets understand this with an example:
Consider x = 123 is the given number. Lets take a temporary variable to store this given number, lets say tmp (this step is necessary because we need the original number x unmodified so that it can be compared with the reversed number in the final step). Also take a variable to store the reversed number, lets call it reversedNum. Initially reversedNum = 0.
One by one we process each digit in tmp starting with the last digit 3. Extract last digit from tmp using the mod operator i.e. lastDigit = tmp%10 = 123 % 10 = 3.
Next step is to move lastDigit to its correct base position in reversedNum. This step is similar to the leetcode 8 problem where we had to move converted digit to its correct base position. As in leetcode 8 problem we can accomplish this by multiplying reversedNum with 10 and then adding the lastDigit to it. So reversedNum = reversedNum * 10 + lastDigit = 0 * 10 + 3 = 3.
Now that we have processed the last digit completely we need to remove it from tmp. We can do this using the divide operation, tmp = tmp/10 = 123/10 = 12.
Repeat the above three steps again for digit 2 in tmp = 12.
lastDigit = tmp%10 = 12 % 10 = 2
reversedNum = reversedNum * 10 + lastDigit = 3 * 10 + 2 = 32
tmp = tmp/10 = 12/10 = 1.
Again we repeat these steps for the final digit in tmp = 1.
lastDigit = tmp%10 = 1 % 10 = 1
reversedNum = reversedNum * 10 + lastDigit = 32 * 10 + 1 = 321
tmp = tmp/10 = 1/10 = 0
As you can see we have successfully reversed the given number 123. Now we compare the reversedNum 321 with original number x = 123, clearly these two are not equal, so it is not a palindrome, therefore we return a boolean false as result.
We do all these operations in a loop. Once tmp = 0 we stop our loop.
Note: We perform mod the given number specifically with 10 (and not some other number) because, when we do mod on any given number the remainder would result in the unit's place digit of that number.
For Example: 123%10 = 3 (% is the mod or modulus symbol, which gives the remainder of the division as the result). We use %10 in this case to extract the unit's place digit in the number. But if we use any other number, it would not give us the exact digit.
Implementation
Language: Go
Complexity Analysis
Time Complexity: O(d)
d here is the no. of digits in the given input number. Time complexity is O(d) because we have to check each digit in the given number at least once to determine if the given number is a palindrome.
Space Complexity: O(1)
No extra space is used.
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
Solution 2: Optimized solution 1
In solution 1 we are using extra space to store the input number in a temporary variable tmp. We do this because we need the original number x in order to compare it with the reversed number and therefore cannot manipulate the original number x.
However we can avoid using the tmp variable by slightly modifying solution 1.
The idea is to do the steps mentioned here to reverse the given number only up to the middle digit in x and then compare x with the reversedNum. Basically what we do here is reverse only half of the given number x and compare x with reversed number.
This algorithm involves the following steps:
Reverse half of the digits of the given number x. (Reversing is done using same steps described in solution 1).
Once half of the digits in x are reversed, reversedNum will contain the reversed second half of the original input number and x (modified) will contain the first half of the original input number. For example if the given input is x = 123321, then after reversing half of the digits, reversedNum will be 123 and modified x will be 123.
Now compare the modified x with the reversedNum.
If both x and reversedNum are equal then return true as result, otherwise return false.
Let take one more example to understand this. Consider x = 1221 is the given number, our algorithm reverses the last two digits in x i.e. 21 (until middle digit). So, at the end of our loop x = 12 and reversedNum = 12. Now compare (x, reversedNum) and return the result.
Note: If x contains odd number of digits as in x = 12321, at the end of our loop reversedNum = 123 and x = 12. So we need to divide reversedNum by 10 if x contains odd number of digits before comparing x and reversedNum.
Implementation
Language: Go
Language: Python
Language: Java
Complexity Analysis
Time Complexity: O(d/2)
d here is the no. of digits in the given input number. Time complexity of this algorithm is O(d/2) because we only have to check half of the digits in the given number x (last to middle) to determine if the given number is a palindrome.
Space Complexity: O(1)
No extra space is used.
That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.
If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).
You can explore more such amazing articles from code recipe in our blogs section.
Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time: Join now
Thanks for good explanation .I was surprised with the solution 2 because of do not using a temporary variable . Sorry because my English is not good
Great explanation! Thank you. But I believe there is an error here in regard to Space Complexity. Using a single variable `tmp` repeatedly in a loop does not increase Space Complexity, because there is only one integer `tmp` variable stored in a memory at any given time. Therefore for both solutions the Space Complexity is actually O(1).
thank u so much, good explanation, keep up the good work guys