Palindrome Number Solution for Accenture
Company: Accenture · Difficulty: Easy · Topics: Math
Problem Statement
Given an integer x, return true if x is a palindrome, and false otherwise.
Key Understanding:
- A palindrome number reads the same forwards and backwards
- We need to check if the number is symmetric around its center
- Negative numbers are never palindromes (due to the minus sign)
- Numbers ending with 0 (except 0 itself) are never palindromes
- We need to handle both even and odd length numbers
Examples
Example 1:
Input: x = 121
Output: true
Explanation:
- 121 reads as "121" from left to right
- 121 reads as "121" from right to left
- Both are the same, so it's a palindrome
- Visual representation: 1 2 1 → 1 2 1 ✓
Example 2:
Input: x = -121
Output: false
Explanation:
- -121 reads as "-121" from left to right
- -121 reads as "121-" from right to left
- They are different, so it's not a palindrome
- Visual representation: -1 2 1 → 1 2 1- ✗
Example 3:
Input: x = 10
Output: false
Explanation:
- 10 reads as "10" from left to right
- 10 reads as "01" from right to left
- They are different, so it's not a palindrome
- Visual representation: 1 0 → 0 1 ✗
Example 4:
Input: x = 12321
Output: true
Explanation:
- 12321 reads as "12321" from left to right
- 12321 reads as "12321" from right to left
- Both are the same, so it's a palindrome
- Visual representation: 1 2 3 2 1 → 1 2 3 2 1 ✓
Example 5:
Input: x = 0
Output: true
Explanation:
- 0 reads as "0" from left to right
- 0 reads as "0" from right to left
- Both are the same, so it's a palindrome
- Note: 0 is a special case (ends with 0 but is a palindrome)
Intuition
The key insight is that we can check if a number is a palindrome by comparing it with its reverse. However, we can optimize this by only reversing half of the number.
Core Concept:
- A palindrome number is symmetric around its center
- We can reverse half of the number and compare it with the remaining half
- This avoids the need to reverse the entire number
- We can stop when the reversed half becomes greater than or equal to the remaining half
Why Reverse Half Works:
- For even-length numbers: both halves should be equal
- For odd-length numbers: the reversed half should equal the remaining half (ignoring the middle digit)
- This approach is more efficient than reversing the entire number
Approach
Approach 1: Reverse Half (Optimal)
Algorithm:
1. Handle edge cases:
- If x < 0, return false (negative numbers are never palindromes)
- If x != 0 and x % 10 == 0, return false (numbers ending with 0 except 0 itself)
2. Initialize reversed_num = 0
3. While x > reversed_num:
- reversed_num = reversed_num * 10 + x % 10
- x = x / 10
4. Check if x == reversed_num (even length) or x == reversed_num / 10 (odd length)
5. Return true if either condition is met
Why This Works:
- We only reverse half of the number, making it more efficient
- For even-length numbers: both halves should be equal
- For odd-length numbers: the middle digit is ignored in comparison
- We stop when reversed_num becomes >= x to avoid unnecessary work
Complexity Analysis:
- Time: O(log n) - We process approximately half the digits
- Space: O(1) - Only constant variables needed
Approach 2: Convert to String
Algorithm:
1. Convert the number to a string
2. Use two pointers: left at start, right at end
3. While left < right:
- Compare characters at left and right positions
- If they don't match, return false
- Move left pointer right, right pointer left
4. Return true if all characters match
Why This Works:
- String representation makes it easy to compare characters
- Two pointers can efficiently check symmetry
- Simple and intuitive approach
Complexity Analysis:
- Time: O(log n) - Converting to string and comparing
- Space: O(log n) - String storage needed
Approach 3: Full Reverse
Algorithm:
1. Handle negative numbers (return false)
2. Reverse the entire number
3. Compare the reversed number with the original
4. Return true if they are equal
Why This Works:
- A palindrome number equals its reverse
- Simple and straightforward approach
- Works for all positive numbers
Complexity Analysis:
- Time: O(log n) - We reverse all digits
- Space: O(1) - Only constant variables needed
Dry Run
Let's trace through Example 1: x = 121
Reverse Half Approach:
Initial State: x = 121, reversed_num = 0
Step 1: x = 121, reversed_num = 0
- x > reversed_num: 121 > 0 ✓
- reversed_num = 0 * 10 + 121 % 10 = 0 + 1 = 1
- x = 121 / 10 = 12
Step 2: x = 12, reversed_num = 1
- x > reversed_num: 12 > 1 ✓
- reversed_num = 1 * 10 + 12 % 10 = 10 + 2 = 12
- x = 12 / 10 = 1
Step 3: x = 1, reversed_num = 12
- x > reversed_num: 1 > 12 ✗ (stop the loop)
Step 4: Check conditions
- x == reversed_num: 1 == 12 ✗
- x == reversed_num / 10: 1 == 12 / 10 = 1 ✓
- Return true
String Approach:
Step 1: Convert to string
- str = "121"
Step 2: Two pointer comparison
- left = 0, right = 2
- str[0] = '1', str[2] = '1' ✓
- left = 1, right = 1
- left >= right, stop
- Return true
Full Reverse Approach:
Step 1: Reverse the number
- original = 121
- reversed = 0
- reversed = 0 * 10 + 1 = 1, original = 12
- reversed = 1 * 10 + 2 = 12, original = 1
- reversed = 12 * 10 + 1 = 121, original = 0
Step 2: Compare
- original = 121, reversed = 121
- 121 == 121 ✓
- Return true
Key Insights
1. Half Reversal: Only need to reverse half the number for efficiency
2. Negative Numbers: Always false due to minus sign
3. Trailing Zeros: Numbers ending with 0 (except 0) are never palindromes
4. Odd vs Even Length: Handle middle digit differently for odd-length numbers
5. Early Termination: Stop when reversed half >= remaining half
Edge Cases
1. Negative Numbers: Always return false
2. Zero: Special case - is a palindrome
3. Single Digit: Always a palindrome
4. Numbers Ending with 0: Never palindromes (except 0)
5. Large Numbers: Handle integer overflow in reversal
6. Odd vs Even Length: Different comparison logic needed
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 Half (Optimal)
Time Complexity: O(log n) - We process half the digits
Space Complexity: O(1) - We use only constant extra space
Advantages:
- Most efficient approach
- Constant space usage
- Handles all edge cases correctly
- No string conversion needed
Disadvantages:
- Requires understanding of number manipulation
- May be less intuitive than string approach
Solution 2: Convert to String
Time Complexity: O(log n) - We convert to string and compare
Space Complexity: O(log n) - We need string storage
Advantages:
- Very intuitive and easy to understand
- Simple implementation
- Easy to debug and trace
Disadvantages:
- Uses extra space for string
- Requires string manipulation
- Slightly less efficient than mathematical approach
Solution 3: Full Reverse
Time Complexity: O(log n) - We reverse all digits
Space Complexity: O(1) - We use only constant extra space
Advantages:
- Simple and straightforward
- Constant space usage
- Easy to understand logic
Disadvantages:
- Less efficient than half reversal
- Reverses more digits than necessary
- May have integer overflow issues with large numbers