Palindrome Number Solution for Capgemini
Company: Capgemini · Difficulty: Easy · Topics: Math
Problem Statement
Given an integer x, return true if x is a palindrome, and false otherwise.
A number is a palindrome when it reads the same backward as forward.
Examples
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.
Example 4:
Input: x = 12321
Output: true
Explanation:
12321 reads as 12321 from left to right and from right to left.
Example 5:
Input: x = 0
Output: true
Explanation:
Single digit 0 is a palindrome.
Intuition
The key insight is to reverse the number and compare it with the original. If they are equal, the number is a palindrome.
This works because:
- A palindrome reads the same forward and backward
- Reversing the number gives us the "backward" version
- If original equals reversed, it's a palindrome
- Negative numbers can never be palindromes due to the minus sign
Approach
Approach 1: Reverse Number (Optimal)
1. Handle negative numbers (they are never palindromes)
2. Reverse the number by extracting digits from right to left
3. Compare the reversed number with the original
4. Return true if they are equal, false otherwise
Approach 2: String Conversion
1. Convert the number to a string
2. Use two pointers to compare characters from both ends
3. Move pointers towards center until they meet
Approach 3: Half Reversal
1. Only reverse the second half of the number
2. Compare first half with reversed second half
3. More efficient as we only reverse half the digits
Dry Run
Let's trace through Example 1: x = 121
Reverse Number Approach:
- original = 121, reversed = 0
- x = 121: digit = 1, reversed = 0*10 + 1 = 1, x = 12
- x = 12: digit = 2, reversed = 1*10 + 2 = 12, x = 1
- x = 1: digit = 1, reversed = 12*10 + 1 = 121, x = 0
- original (121) == reversed (121) → return true
String Approach:
- Convert to string: "121"
- left = 0, right = 2: "1" == "1" ✓
- left = 1, right = 1: "2" == "2" ✓
- left = 2, right = 0: pointers crossed → return true
Half Reversal Approach:
- Count digits: 3 (odd)
- Reverse second half: 121 → 12, reversed = 21
- Compare: 1 == 1 ✓ → return true
Key Insights
1. Negative Numbers: All negative numbers are not palindromes
2. Single Digits: All single digit numbers (0-9) are palindromes
3. Reversal Logic: Extract digits from right to left using modulo and division
4. Efficiency: Half reversal is more efficient for large numbers
Edge Cases
1. Negative numbers: Always return false
2. Single digit: Always return true (0-9)
3. Zero: Return true
4. Large numbers: Handle overflow in reversal
5. Numbers ending with 0: Can't be palindromes (except 0)
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Reverse Number (Optimal)
Time Complexity: O(log n) - Number of digits in the number
Space Complexity: O(1) - Constant extra space
Solution 2: String Conversion
Time Complexity: O(log n) - Convert to string and compare
Space Complexity: O(log n) - Space for string conversion
Solution 3: Half Reversal
Time Complexity: O(log n) - Only reverse half the digits
Space Complexity: O(1) - Constant extra space