Palindrome Number
Problem Description
Given an integer x, return true if x is a palindrome, and false otherwise.
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:
- -231 <= x <= 231 - 1
Follow up: Could you solve it without converting the integer to a string?
Solve it on LeetCode
Approaches
1. Convert Number to String
Intuition:
The simplest way to determine if a number is a palindrome is to convert it to a string and check if the string reads the same forwards and backwards.
- Convert the integer to a string.
- Compare the original string with its reverse. If they are the same, then the number is a palindrome.
Code:
- Time Complexity: O(n), where n is the number of digits in the number because we compare each character.
- Space Complexity: O(n), due to the storage used by the string representation of the number.
2. Reversing Digits Approach
Intuition:
Instead of converting the integer to a string, we can reverse the digits of the integer itself and compare it with the original integer.
- Handle edge cases for negative numbers and single-digit numbers.
- Reverse the digits of the number.
- Compare the reversed number with the original number.
Code:
Complexity Analysis:
- Time Complexity: O(n), where n is the number of digits in the number.
- Space Complexity: O(1), since we're only using a few integers for temporary storage.
3. Reversing Half of the Number
Intuition:
We can improve upon the previous approach by only reversing half of the number and checking if the first half equals the reversed second half. This reduces the amount of work needed, particularly for very long numbers.
- A number is a palindrome if dividing and reversing its first half equals the second half.
- Reverse the second half of the number and compare it with the first half.
Code:
- Time Complexity: O(log n), because we're processing roughly half of the number's digits.
- Space Complexity: O(1), as we only use a few integer variables for temporary storage.