9. Palindrome Number
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 50.0%
Problem Breakdown
The problem asks us to determine if a given integer x is a palindrome. An integer is considered a palindrome if it reads the same backward as forward. The input is a single integer, and the output should be a boolean value (true or false).
Inputs:
- A single integer
x.
Outputs:
- A boolean indicating whether
xis a palindrome.
Implicit Constraints/Edge Cases:
- Negative numbers are not palindromes because of the negative sign.
- Numbers ending in zero (except 0 itself) cannot be palindromes since they would have a leading zero when reversed.
- The integer range is constrained by
-2^31to2^31 - 1.
Intuition
A brute-force approach would involve converting the integer to a string and then checking if the string reads the same backward as forward. This method is straightforward but has a time complexity of O(n) due to the string reversal operation, where n is the number of digits in the integer.
However, we can improve this by avoiding string conversion. The key insight is to reverse only half of the number and compare it with the other half. This reduces the space complexity to O(1).
Approach
To solve this problem without converting the integer to a string, we can follow these steps:
- Handle Negative Numbers: If
xis negative, returnfalseimmediately since negative numbers cannot be palindromes. - Reverse Half of the Number:
- Initialize two variables:
reversed_half = 0andoriginal = x. - While
x > reversed_half, extract the last digit ofxusingx % 10and add it toreversed_halfafter shifting its digits one place to the left (reversed_half * 10 + x % 10). - Remove the last digit from
xby performing integer division (x //= 10).
- Initialize two variables:
- Compare the Halves:
- If the number of digits in
originalis odd, ignore the middle digit by comparingreversed_half // 10withx. - Otherwise, compare
reversed_halfwithx.
- If the number of digits in
Complexity Analysis
- Time Complexity: O(log n), where n is the number of digits in the integer. This is because we are processing each digit of the number once.
- Space Complexity: O(1). We are using a constant amount of extra space regardless of the input size.
Solution
def isPalindrome(x: int) -> bool:
# Negative numbers cannot be palindromes
if x < 0:
return False
reversed_half = 0
original = x
while x > reversed_half:
reversed_half = reversed_half * 10 + x % 10
x //= 10
# If the number of digits is odd, ignore the middle digit
return x == reversed_half or original // 10 == reversed_half
Edge Cases Handled
- Negative Numbers: The function returns
falseimmediately for negative numbers. - Numbers Ending in Zero (except 0 itself): These are handled by the condition where
x > reversed_half, ensuring that only valid palindromes are considered. - Single-digit Numbers: Single-digit numbers are inherently palindromes and will return
true. - Zero: The function correctly identifies zero as a palindrome.