9. Palindrome Number

🟩 Easy

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

An integer is a palindrome when it reads the same forward and backward.

For example, 121 is a palindrome while 123 is not.

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

• -2^31 <= x <= 2^31-1

Solution

My Solution (Full Reversal)

func isPalindrome(x int) bool {
    if x < 0 {
        return false
    }

    num := 0
    k := x
    for k != 0 {
        num *= 10
        num += k % 10
        k /= 10
    }

    return x == num
}

Optimal Solution (Half Reversal)

func isPalindrome(x int) bool {
    // Handle negative and numbers ending with 0
    if x < 0 || (x != 0 && x%10 == 0) {
        return false
    }
    
    reversed := 0
    // Only reverse half of the number
    for x > reversed {
        reversed = reversed*10 + x%10
        x /= 10
    }
    
    // For even length: x == reversed
    // For odd length: x == reversed/10
    return x == reversed || x == reversed/10
}

Approach Analysis

This problem can be solved in multiple ways:

1. Full Reversal (Your Solution):

   • Reverse entire number

   • Compare with original

   • Simple to understand

   • Handles all cases

2. Half Reversal (Optimal):

   • Only reverse half the digits

   • Compare middle when done

   • More efficient

   • Handles overflow naturally

Visualization of Both Approaches

Full Reversal Process (Your Solution)

Input: x = 12321

Step 1: Build reversed number
12321 → digit = 1, rev = 1
1232  → digit = 2, rev = 12
123   → digit = 3, rev = 123
12    → digit = 2, rev = 1232
1     → digit = 1, rev = 12321

Step 2: Compare
12321 == 12321 → true

Half Reversal Process (Optimal)

Input: x = 12321

While x > reversed:
12321 → rev = 1,     x = 1232
1232  → rev = 12,    x = 123
123   → rev = 123,   x = 12

Compare:
12 == 123/10 (12) → true

Complexity Analysis

Full Reversal (Your Solution)

• Time: O(log₁₀n)

  • Process all digits

  • n is the input number

  • Each digit needs one iteration

• Space: O(1)

  • Only use one extra variable

  • Constant extra space

  • No additional data structures

Half Reversal (Optimal)

• Time: O(log10n)

  • Process half the digits

  • Slightly faster in practice

  • Early termination possible

• Space: O(1)

  • Only use reversed number

  • Constant extra space

  • No risk of overflow

Why Half Reversal Works

1. Mathematical Insight:

   • Palindrome is symmetric

   • Only need to check half

   • Middle digit doesn't matter

   • Works for both even/odd lengths

2. Optimization Benefits:

   • Half the operations

   • No overflow possible

   • Early termination

   • Handles edge cases elegantly

When to Use Each Approach

1. Full Reversal When:

   • Learning number manipulation

   • Code clarity is priority

   • Need the full reversed number

   • Teaching basic concepts

2. Half Reversal When:

   • Performance is critical

   • Large numbers expected

   • Memory constraints

   • Production code

Common Patterns & Applications

1. Related Problems:

   • Reverse Integer

   • Valid Palindrome

   • Palindrome Linked List

   • Palindrome Pairs

2. Key Techniques:

   • Digit manipulation

   • Two-pointer concept

   • Number reversal

   • Middle finding

Interview Tips

1. Solution Highlights:

   • Handle negative numbers

   • Consider trailing zeros

   • Optimize for half comparison

   • No string conversion needed

2. Common Pitfalls:

   • Missing negative check

   • Overflow issues

   • Wrong middle handling

   • Edge cases with zero

3. Testing Strategy:

   • Single digit

   • Even length numbers

   • Odd length numbers

   • Negative numbers

   • Numbers ending in zero

4. Follow-up Questions:

   • Handle decimal numbers?

   • Different number bases?

   • Optimize space usage?

   • Stream of digits?

result

Leetcode: link