LeetCode Solution: Palindrome Number

Problem Description

Given an integer x, return true if x is a palindrome, and false otherwise.

A palindrome number reads the same forward and backward.

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-, thus not a palindrome

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left, thus not a palindrome

Solution 1: String Conversion (Most Intuitive)

Approach

Convert the number to a string and check if the string equals its reverse.

Code

def isPalindrome(x):
    s = str(x)
    return s == s[::-1]

Execution Process

x = 121
s = "121"
s[::-1] = "121"
"121" == "121" → True

Complexity Analysis

• Time Complexity: O(log x)
  • Number to string conversion: O(log x)
  • String reversal: O(log x)
  • String comparison: O(log x)
• Space Complexity: O(log x)
  • Extra space needed for string and its reverse

Pros and Cons

Pros:

• ✅ Extremely concise (only 2 lines)
• ✅ Intuitive and easy to understand
• ✅ No need to handle mathematical edge cases

Cons:

• ❌ Requires O(log x) extra space
• ❌ String operations are slower than math operations
• ❌ Creates two string objects

Solution 2: Mathematical Approach - Reverse Half (Optimal)

Core Idea

Instead of reversing the entire number, we only reverse the second half and compare it with the first half.

Key Observations

1. Negative numbers are never palindromes (due to the minus sign)
2. Numbers ending with 0 are not palindromes (except 0 itself)
3. The first and second halves of a palindrome are symmetric

Code

def isPalindrome(x):
    # Handle edge cases
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    
    reversed_half = 0
    # Reverse the second half of the number
    while x > reversed_half:
        reversed_half = reversed_half * 10 + x % 10
        x //= 10
    
    # Even length: x == reversed_half
    # Odd length: x == reversed_half // 10 (remove middle digit)
    return x == reversed_half or x == reversed_half // 10

Detailed Execution Analysis

Example 1: Even-length Palindrome (x = 1221)

Initial: x = 1221, reversed_half = 0

Round 1:
- x % 10 = 1 (extract last digit)
- reversed_half = 0 * 10 + 1 = 1
- x = 1221 // 10 = 122
- Condition: 122 > 1, continue

Round 2:
- x % 10 = 2 (extract last digit)
- reversed_half = 1 * 10 + 2 = 12
- x = 122 // 10 = 12
- Condition: 12 == 12, stop

Result: x (12) == reversed_half (12) ✓ Is palindrome

Example 2: Odd-length Palindrome (x = 12321)

Initial: x = 12321, reversed_half = 0

Round 1:
- x % 10 = 1
- reversed_half = 0 * 10 + 1 = 1
- x = 12321 // 10 = 1232
- Condition: 1232 > 1, continue

Round 2:
- x % 10 = 2
- reversed_half = 1 * 10 + 2 = 12
- x = 1232 // 10 = 123
- Condition: 123 > 12, continue

Round 3:
- x % 10 = 3
- reversed_half = 12 * 10 + 3 = 123
- x = 123 // 10 = 12
- Condition: 12 < 123, stop

Result: x (12) == reversed_half // 10 (123 // 10 = 12) ✓ Is palindrome

Visual Understanding

Even length (1221):
Original: [1][2][2][1]
           ↓   ↓
        First  Second
         12 == 12 ✓

Odd length (12321):
Original: [1][2][3][2][1]
           ↓   ↓   ↓
        First Mid Second
         12  (3)   21
         12 == 12 ✓ (middle 3 doesn't matter)

Why while x > reversed_half?

This condition ensures we process until the middle of the number:

• Each iteration: x loses one digit, reversed_half gains one
• When they “meet,” we’ve processed half the digits

Complexity Analysis

• Time Complexity: O(log x)
  • Only process half the digits
  • Loop runs log₁₀(x) / 2 times
• Space Complexity: O(1)
  • Only uses two integer variables

Solution 3: Full Number Reversal (Not Recommended)

Code

def isPalindrome(x):
    if x < 0:
        return False
    
    original = x
    reversed_num = 0
    
    while x > 0:
        reversed_num = reversed_num * 10 + x % 10
        x //= 10
    
    return original == reversed_num

Why Not Recommended?

1. Integer overflow risk: Reversed number might exceed integer range
2. Less efficient: Needs to process all digits
3. Doesn’t leverage palindrome properties

Performance Comparison

import time

def test_performance():
    test_cases = [121, 1221, 12321, 123454321, -121, 10, 0] * 100000
    
    # Test string solution
    start = time.time()
    for x in test_cases:
        s = str(x)
        result = s == s[::-1]
    string_time = time.time() - start
    
    # Test mathematical solution
    start = time.time()
    for x in test_cases:
        if x < 0 or (x % 10 == 0 and x != 0):
            result = False
        else:
            temp, reversed_half = x, 0
            while temp > reversed_half:
                reversed_half = reversed_half * 10 + temp % 10
                temp //= 10
            result = temp == reversed_half or temp == reversed_half // 10
    math_time = time.time() - start
    
    print(f"String solution: {string_time:.3f} seconds")
    print(f"Math solution: {math_time:.3f} seconds")
    print(f"Math solution is {string_time/math_time:.2f}x faster")

Typical Results:

String solution: 0.842 seconds
Math solution: 0.513 seconds
Math solution is 1.64x faster

Solution Selection Guide

When to Use String Solution

• Limited interview time, need quick implementation
• Code readability is priority
• Team has beginners who need to maintain the code

When to Use Mathematical Solution

• Performance is critical
• Memory usage is constrained
• Processing large amounts of data
• Demonstrating algorithmic skills

Key Takeaways

1. Importance of Edge Cases

   • Always handle special cases first (negative numbers, trailing zeros)
   • Simplifies subsequent logic

2. Algorithm Optimization Process

   • Start with intuitive solution
   • Analyze bottlenecks (space, time)
   • Leverage problem properties (only need half)

3. Code Quality Trade-offs

   • Readability vs Performance
   • Simplicity vs Completeness
   • Choose based on actual requirements

Interview Bonus Points

1. Discuss Multiple Solutions: Shows comprehensive thinking
2. Analyze Complexity: Demonstrates theoretical foundation
3. Consider Edge Cases: Shows code rigor
4. Discuss Real-world Applications: Shows engineering mindset

Extended Practice

1. Implement without using strings or division
2. If converting to array is allowed, how to optimize?
3. For string palindrome checking, what optimizations exist?

Mastering multiple solutions to this problem not only solves the palindrome number question but more importantly teaches how to analyze and optimize algorithms!