grid47 Exploring patterns and algorithms
Nov 6, 2024
5 min read
Solution to LeetCode 9: Palindrome Number Problem
Given an integer, return true if the number is a palindrome. A number is a palindrome if it reads the same forwards and backwards. If the number is negative, it is automatically not a palindrome.
Problem
Approach
Steps
Complexity
Input: The input is a single integer x. The number can be negative or positive.
Example: Input: x = 121
Constraints:
• -231 <= x <= 231 - 1
Output: Return a boolean value indicating whether the input integer is a palindrome or not.
Example: Output: true
Constraints:
• Return true if the number is a palindrome, false otherwise.
Goal: To check if a given number is a palindrome without converting the integer to a string.
Steps:
• Check if the number is negative. If it is, return false immediately.
• Reverse the digits of the number.
• Compare the original number with the reversed number. If they are the same, return true; otherwise, return false.
Goal: The number x can be a negative or positive integer, and the solution must handle both cases efficiently.
Steps:
• The number should be within the range of a 32-bit signed integer (-2^31 <= x <= 2^31 - 1).
• The solution should not convert the integer to a string.
Assumptions:
• We are guaranteed that the input will be within the specified range (-231 <= x <= 231 - 1).
• Negative numbers are not palindromes.
• Input: Input: x = 121
• Explanation: The number 121 reads the same from left to right and right to left, so it is a palindrome.
• Input: Input: x = -121
• Explanation: The number -121 is not a palindrome because the negative sign appears only on the left, not the right.
• Input: Input: x = 10
• Explanation: The number 10 is not a palindrome because it reads '01' from right to left, which is not the same as the original number.
Approach: To check if a number is a palindrome, we reverse its digits and compare the reversed number with the original. We will handle negative numbers immediately as they can never be palindromes.
Observations:
• A simple approach is to reverse the digits and check if the original and reversed numbers match.
• We need to handle negative numbers early since they can't be palindromes.
• We must reverse the digits without converting the number to a string, which can be done by manipulating the number mathematically.
Steps:
• Check if the number is negative. If it is, return false.
• Reverse the digits of the number using a mathematical approach (by taking modulo 10 and dividing the number).
• Compare the original number with the reversed number. If they are equal, return true, otherwise return false.
Empty Inputs:
• The input is always a valid integer within the specified range.
Large Inputs:
• The solution should handle the largest integer values within the range efficiently.
Special Values:
• If the number is negative, it will not be a palindrome.
• If the number ends with a zero and is greater than zero, it cannot be a palindrome.
Constraints:
• Do not convert the number to a string. Reverse the digits mathematically.
boolisPalindrome(int x) {
if(x <0) returnfalse;
longlongint y = x, z =0;
while(x) {
z = z *10+ x %10;
x /=10;
}
return y == z;
}
1 : Function Declaration
boolisPalindrome(int x) {
Declare the `isPalindrome` function, which takes an integer `x` as input and returns a boolean indicating whether it's a palindrome.
2 : Conditional Check
if(x <0) returnfalse;
Check if the input number `x` is negative. Negative numbers cannot be palindromes, so return `false` immediately.
3 : Variable Initialization
longlongint y = x, z =0;
Initialize two variables: `y` to store a copy of the original number `x`, and `z` to store the reversed number.
4 : Loop Iteration
while(x) {
Start a loop that continues while `x` is not zero.
5 : Mathematical Operations
z = z *10+ x %10;
Extract the last digit of `x` using the modulo operator and append it to the reversed number `z`.
6 : Integer Division
x /=10;
Remove the last digit from `x` by integer division.
7 : Return Value
return y == z;
Compare the original number `y` with the reversed number `z`. If they are equal, the number is a palindrome, so return `true`. Otherwise, return `false`.
Best Case: O(log(x)), where x is the integer. This is because we reverse the digits of the number, and the number of digits is proportional to log(x).
Average Case: O(log(x))
Worst Case: O(log(x)), since we are iterating over all digits to reverse the number.
Description: The time complexity is logarithmic relative to the size of the integer.
Best Case: O(1)
Worst Case: O(1), since we only use a constant amount of extra space for the reversal.
Description: The space complexity is constant as we only use a few variables to store intermediate values.
