Leetcode 9. Palindrome Number
Problem Explanation:
The problem is asking to identify if an integer is a palindrome. A palindrome is a number or a sequence that remains the same when its digits are reversed. For instance, '121' is a palindrome, but '123' is not.
This problem can be approached by using a while loop to reverse the digit and checks if input integer and reversed integer are same or not.
Solution Explanation:
The solution involves the concept of numbers and while loop. Here's how it works:
First, it checks if the number is negative. If it is, it immediately returns false
, because negative numbers cannot be a palindrome.
For other numbers, a while loop is used to reverse the number. The reversed number is built up from the bottom and the original number is divided by 10 at each step, until it becomes zero.
Finally, it checks whether the original number and the reversed number are the same.
For example, let's take the number 121. The loop reverses this number as follows:
- The remainder of 121 divided by 10 is 1. This become the first digit of the reversed number.
- We divide 121 by 10, which gives 12.
- The reminder of 12 divided by 10 is 2. This become the next digit of the reversed number.
- We divide 12 by 10, which gives 1.
- The reminder of 1 divided by 10 is 1. This become the last digit of the reversed number.
- We divide 1 by 10, which gives 0. The loop stops here.
We end up with 121, which is the same as the original number, so the function return true
.
Python Solution:
1 2python 3class Solution: 4 def isPalindrome(self, x: int) -> bool: 5 if x < 0: 6 return False 7 else: 8 temp = x 9 reverse = 0 10 while(x > 0): 11 digit = x % 10 12 reverse = reverse * 10 + digit 13 x = x // 10 14 if temp == reverse: 15 return True 16 return False
Java Solution:
1 2java 3class Solution { 4 public boolean isPalindrome(int x) { 5 if (x < 0) { 6 return false; 7 } 8 int orginal = x; 9 int reverse = 0; 10 while (x != 0) { 11 int d = x % 10; 12 reverse = reverse * 10 + d; 13 x /= 10; 14 } 15 return orginal == reverse; 16 } 17}
JavaScript Solution:
1 2javascript 3var isPalindrome = function(x) { 4 if (x < 0) { 5 return false; 6 } 7 var reversed = 0, y = x; 8 while (y) { 9 reversed = reversed * 10 + y % 10; 10 y = Math.floor(y / 10); 11 } 12 return reversed === x; 13};
C++ Solution:
1 2c++ 3class Solution { 4public: 5 bool isPalindrome(int x) { 6 if (x < 0) 7 return false; 8 9 long reversed = 0; 10 int y = x; 11 12 while (y) { 13 reversed = reversed * 10 + y % 10; 14 y /= 10; 15 } 16 17 return reversed == x; 18 } 19};
C# Solution:
1 2csharp 3public class Solution { 4 public bool isPalindrome(int x) { 5 if (x < 0) { 6 return false; 7 } 8 int orginal = x; 9 int reverse = 0; 10 while (x != 0) { 11 int d = x % 10; 12 reverse = reverse * 10 + d; 13 x /= 10; 14 } 15 return orginal == reverse; 16 } 17}
The above solutions have a linear time complexity. As we are iterating through each digit in the number, the time complexity is O(log10(n)) where n is the input number.The space complexity is also minimal, as we only need a few integer variables for storing digits, the modified number, and the reversed number.
Given their simplicity and efficiency, these solutions should function well for the problem of identifying palindromic integers.
The presented solutions in Python, Java, JavaScript, C++, and C# have the same underlying logic because it is not language-specific but a general algorithm to solve the problem.
This problem also illustrates the importance of understanding the properties of numbers and mathematical operations when solving algorithmic challenges. A solid grasp of math can lead to clean, efficient solutions.
Wrapping Up, we saw how to reverse a given integer and then use that reversed integer to solve the problem of determining whether the original integer was a palindrome or not. Through the implementations across Python, Java, Javascript, C++ and C#, we noted that while the syntax varies across languages, the core logic stayed the same. Understanding how to reverse a number and learning how that can be used to check for a property - isPalindrome - is a fantastic illustration of algorithmic problem-solving.
Happy Coding!
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.