Palindrome Number

• Difficulty: Easy
• Topics: Math
• Link: https://leetcode.com/problems/palindrome-number/

Problem Description

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

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:

• -231 <= x <= 231 - 1

Follow up: Could you solve it without converting the integer to a string?

Solution

Comprehensive Solution: Palindrome Number

1. Problem Deconstruction

Rewrite the Problem

Technical Definition:
Given a signed 32-bit integer x, return a boolean indicating whether the decimal representation of x (in base-10, without extraneous leading zeros except for the number 0 itself) exhibits reflectional symmetry about its center when read left-to-right versus right-to-left. Formally, for $x \ge 0$ with $k$ digits $d_{k-1}d_{k-2}\dots d_0$ where $x = \sum_{i=0}^{k-1} d_i \cdot 10^i$ and $d_{k-1} \ne 0$ unless $k=1$ and $x=0$, the condition is $d_i = d_{k-1-i}$ for all $i \in [0, k-1]$. For $x < 0$, return false due to the leading minus sign.

Beginner-Friendly Explanation:
We’re checking if a number reads the same forwards and backwards, like the word “racecar”. For example, 121 is a palindrome because it’s 121 whether you read left-to-right or right-to-left. However, -121 is not because reversing gives “121-”, which is different. Also, 10 becomes “01” when reversed, so it’s not a palindrome.

Mathematical Formulation:
Let $x \in \mathbb{Z}$ with $-2^{31} \le x \le 2^{31}-1$. Define the digit-extraction function $\text{digits}(x) = [d_0, d_1, \dots, d_{k-1}]$ where $d_i = \lfloor x / 10^i \rfloor \mod 10$ and $k = \lfloor \log_{10} x \rfloor + 1$ for $x > 0$, with $k=1$ for $x=0$. Then $x$ is a palindrome iff $x \ge 0$ and $\forall i \in [0, \lfloor k/2 \rfloor], d_i = d_{k-1-i}$.

Constraint Analysis

• Range: $-2^{31} \le x \le 2^{31}-1$

  • This bounds the number of decimal digits to at most 10 ($2^{31}-1 = 2,147,483,647$ has 10 digits). Thus, any $O(d)$ algorithm where $d$ is digit count runs in effectively constant time.
  • Hidden implication: Numbers ending with 0 (except 0 itself) cannot be palindromes because reversal would produce a leading zero, violating standard integer representation.
  • Edge cases:
    1. $x=0$: Single digit, trivially palindrome.
    2. $x \in [1,9]$: All are palindromes.
    3. Negative numbers: Immediately false due to minus sign.
    4. Numbers with trailing zeros: e.g., 10, 100, 500; all non-palindromic.
    5. Large palindromes within range: e.g., 123454321, 999999999.
    6. Maximum integer 2147483647: Not a palindrome; minimum -2147483648: Not a palindrome.

• Follow-up constraint: “Solve without converting integer to string”

  • Eliminates straightforward string-reversal approaches, forcing mathematical digit manipulation or other integer-only techniques.
  • Implies space optimization: should aim for $O(1)$ auxiliary space.

2. Intuition Scaffolding

Analogies

1. Real-World Metaphor (Mirror Writing):
   Imagine writing the number on a transparent sheet. Holding it up to a mirror, a palindrome number appears identical in the mirror as it does directly. Negative numbers show a minus sign on one side but not the other, breaking the symmetry.

2. Gaming Analogy (Symmetric Puzzle):
   In a tile-matching game where digits are on tiles arranged in a row, you win if the sequence is symmetric about the center. You compare the leftmost tile with the rightmost, moving inward. If all pairs match, you’ve found a palindrome.

3. Mathematical Analogy (Polynomial Symmetry):
   A number is a polynomial evaluated at $x=10$: $f(10) = d_{k-1}10^{k-1} + \dots + d_0$. A palindrome corresponds to a symmetric coefficient vector, i.e., $f(10) = f_{\text{rev}}(10)$ where $f_{\text{rev}}(10) = d_010^{k-1} + \dots + d_{k-1}$.

Common Pitfalls (5+ Intuitive-But-Wrong Approaches)

1. Global Min/Max Reversal: Attempting to reverse the entire number without considering overflow. For $x = 1000000009$, reversed is $9000000001 > 2^{31}-1$, causing 32-bit integer overflow.
2. String Conversion with Negation: Converting $-121$ to string, removing the minus sign, reversing, and comparing yields “121” == “121” → true, incorrectly returning true.
3. Leading Zero Ignorance: For $x=10$, reversing digits yields $01 = 1$, then comparing $10 == 1$ → false, but if one mistakenly treats reversed “01” as numeric 10, error occurs.
4. Half-Reversal Termination Condition: Stopping reversal when $x == \text{reversed}$ instead of $x \le \text{reversed}$ can miss odd-digit palindromes (e.g., 12321).
5. Log10 for Digit Count without Zero Handling: Using $k = \lfloor \log_{10} x \rfloor + 1$ fails for $x=0$ because $\log_{10} 0$ is undefined.
6. Array Reversal Without Negative Check: Storing digits in array and comparing without first checking $x < 0$ would incorrectly treat $-121$ as palindrome.

3. Approach Encyclopedia

Approach 1: Brute Force (Compare All Digit Pairs)

Idea: For each digit position $i$, compare with its symmetric counterpart $k-1-i$ by extracting both digits via division and modulus.

Pseudocode:

function isPalindrome(x):
    if x < 0: return false
    k = digit_count(x)  // Handle x=0 separately
    for i from 0 to floor((k-1)/2):
        left_digit = (x // 10^(k-1-i)) % 10
        right_digit = (x // 10^i) % 10
        if left_digit != right_digit:
            return false
    return true

Complexity Proof:

• Extracting a digit via $(\lfloor x / 10^p \rfloor) \mod 10$ requires $O(p)$ time if computing power, but we can precompute powers. Let $d$ be digit count. Precomputing powers costs $O(d)$. Loop runs $O(d/2)$ times, each extraction $O(1)$ if powers are cached, so total $O(d)$ time.
• Space: $O(d)$ for storing powers of 10, or $O(1)$ if computed on-the-fly with repeated multiplication.

Visualization:

x = 12321, k=5
i=0: left = (12321//10000)%10 = 1, right = (12321//1)%10 = 1 ✓
i=1: left = (12321//1000)%10 = 2, right = (12321//10)%10 = 2 ✓
i=2: middle digit, skip
Return true

Approach 2: Full Mathematical Reversal

Idea: Reverse the entire number mathematically and compare with original.

Pseudocode:

function isPalindrome(x):
    if x < 0: return false
    original = x
    reversed = 0
    while x > 0:
        digit = x % 10
        reversed = reversed * 10 + digit
        x = x // 10
    return original == reversed

Complexity Proof:

• Time: $O(d)$ where $d$ is digit count. Each iteration extracts one digit (constant time), and loop runs $d$ times.
• Space: $O(1)$, only a few integer variables.

Visualization:

original = 121
x=121, reversed=0
Iter1: digit=1, reversed=1, x=12
Iter2: digit=2, reversed=12, x=1
Iter3: digit=1, reversed=121, x=0
121 == 121 → true

Approach 3: Half Reversal (Optimal)

Idea: Reverse only the second half of digits and compare with the first half. Stop when reversed half ≥ remaining half.

Pseudocode:

function isPalindrome(x):
    if x < 0 or (x % 10 == 0 and x != 0):
        return false
    reversed_half = 0
    while x > reversed_half:
        reversed_half = reversed_half * 10 + x % 10
        x = x // 10
    return x == reversed_half or x == reversed_half // 10

Complexity Proof:

• Time: $O(d/2)$ because we only process half the digits. Each iteration does constant work (mod, division, multiplication, addition).
• Space: $O(1)$, only two integer variables.

Visualization:

x = 1221, reversed_half = 0
Iter1: x=1221, reversed_half=0+1=1, x=122
Iter2: x=122, reversed_half=10+2=12, x=12
Now x=12 ≤ reversed_half=12 → stop
Check: x == reversed_half? 12 == 12 → true

x = 12321, reversed_half = 0
Iter1: x=12321, reversed_half=1, x=1232
Iter2: x=1232, reversed_half=12, x=123
Iter3: x=123, reversed_half=123, x=12
Stop: x=12 ≤ reversed_half=123
Check: x == reversed_half? 12 == 123? no
Check: x == reversed_half//10? 12 == 12 → true

4. Code Deep Dive

Optimal Solution (Half Reversal) with Line-by-Line Annotations

def isPalindrome(x: int) -> bool:
    # Line 1-2: Immediate rejection of invalid cases
    # Negative numbers cannot be palindromes due to minus sign
    # Numbers ending with 0 (except 0) cannot be palindromes because
    # reversal would have leading zero, changing the value
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    
    # Line 3: Initialize reversed half accumulator
    # This will store the second half of digits in reversed order
    reversed_half = 0
    
    # Line 4-6: Reverse second half until we reach or pass the midpoint
    # Condition x > reversed_half ensures we stop at or before the center
    # For odd-digit numbers, reversed_half ends up with one extra digit
    while x > reversed_half:
        # Extract last digit of current x and append to reversed_half
        reversed_half = reversed_half * 10 + x % 10
        # Remove last digit from x (floor division by 10)
        x //= 10
    
    # Line 7: Final palindrome check
    # Case 1: Even digit count → x exactly equals reversed_half
    # Case 2: Odd digit count → x equals reversed_half without middle digit
    return x == reversed_half or x == reversed_half // 10

Edge Case Handling

• Example 1 (x=121):
  Not negative, not ending with 0. Loop:
  Iter1: reversed_half=1, x=12
  Iter2: reversed_half=12, x=1
  Exit (x=1 ≤ 12). Return 1 == 12//10 (1 == 1) → true ✓

• Example 2 (x=-121):
  First condition triggers (x < 0) → return false immediately ✓

• Example 3 (x=10):
  x % 10 == 0 and x != 0 → return false immediately ✓

• x=0:
  x % 10 == 0 but x == 0, so condition false. Loop not entered (0 > 0 false). Return 0 == 0 or 0 == 0//10 → true ✓

• x=1:
  Loop: reversed_half=1, x=0. Exit. Return 0 == 1 or 0 == 1//10=0 → true ✓

• x=123321 (even digits):
  Loop:
  Iter1: reversed_half=1, x=12332
  Iter2: reversed_half=12, x=1233
  Iter3: reversed_half=123, x=123
  Exit (123 ≤ 123). Return 123 == 123 → true ✓

5. Complexity War Room

Hardware-Aware Analysis

• Digit Count Bound: $d \le 10$ for 32-bit integers, so $O(d)$ is effectively $O(1)$ from an asymptotic perspective.
• CPU Operations: Each iteration performs:
  • One modulus (x % 10) → typically implemented as division remainder
  • One multiplication (reversed_half * 10)
  • One addition
  • One integer division (x // 10)
    All are single-cycle or few-cycle operations on modern ALUs.
• Memory Footprint: Three integer variables (x, reversed_half, temporary for operations) → 12-24 bytes depending on language, easily fitting in CPU registers (L1 cache latency ~0.5 ns).
• Performance at Scale: Even for hypothetical arbitrary-precision integers with $d=10^6$ digits, this algorithm would process ~500,000 iterations, still feasible ($\approx$ 0.5 million operations).

Industry Comparison Table

Approach	Time Complexity	Space Complexity	Readability (1-10)	Interview Viability
Brute Force (all pairs)	$O(d^2)$	$O(1)$ or $O(d)$	6	❌ Too slow for large d
String Conversion & Reverse	$O(d)$	$O(d)$	10	✅ Easy but violates follow-up
Full Mathematical Reversal	$O(d)$	$O(1)$	9	✅ Good, but overflow risk
Half Reversal (Optimal)	$O(d)$	$O(1)$	8	✅ Best: no overflow, minimal operations
Digit Array + Two Pointers	$O(d)$	$O(d)$	9	✅ Clear but extra space

Note: $d$ = number of decimal digits, max 10 for 32-bit integers.

6. Pro Mode Extras

Variants Section

1. Palindrome in Different Bases

   • Problem: Check if $x$ is palindrome in base $b$ (e.g., binary, hexadecimal).
   • Solution: Adapt half-reversal algorithm using base $b$ operations: while $x > \text{reversed}$, do $\text{reversed} = \text{reversed} \cdot b + x \mod b$, $x = \lfloor x / b \rfloor$.

2. Palindrome Linked List (LeetCode 234)

   • Problem: Given singly linked list head, determine if list is palindrome.
   • Solution: Find middle via fast/slow pointers, reverse second half, compare node-by-node with first half, then restore list.

3. Palindrome Permutation (LeetCode 266)

   • Problem: Given string s, determine if a permutation of s could form a palindrome.
   • Solution: Count character frequencies; at most one character can have odd count.

4. Longest Palindromic Substring (LeetCode 5)

   • Problem: Find longest palindrome substring in given string.
   • Solution: Expand around center or dynamic programming.

5. Palindrome Partitioning (LeetCode 131)

   • Problem: Partition s such that every substring is palindrome.
   • Solution: Backtracking with palindrome checking via DP table.

6. Super Palindromes (LeetCode 906)

   • Problem: Find numbers that are palindromes and also squares of palindromes.
   • Solution: Generate palindromes within range, square them, check if square is palindrome.

Interview Cheat Sheet

• First Response: “I’ll check edge cases: negatives → false, numbers ending with 0 (except 0) → false.”
• Complexity Statement: “Since the number of digits is at most 10, any $O(d)$ algorithm is effectively constant time, but I’ll aim for optimal half-reversal to satisfy the no-string constraint.”
• Walkthrough Steps:
  1. Handle negative and trailing-zero cases.
  2. Initialize reversed_half = 0.
  3. While x > reversed_half: reverse last digit onto reversed_half, remove from x.
  4. Compare x with reversed_half (even digits) or reversed_half//10 (odd digits).
• Test Thoroughly:
  • Positive palindromes: 121, 1221, 12321, 1, 0
  • Negative: -121, -1
  • Non-palindromes: 10, 123, 100, -101
• Mention Alternatives: “We could convert to string and compare with reverse, but that uses extra space. The mathematical reversal avoids that, and half-reversal minimizes operations.”
• Error Prevention: “Watch for overflow when reversing entire number; half-reversal avoids that. Also ensure correct handling of odd/even digit counts.”

---

Final Note: The half-reversal algorithm optimally balances efficiency, clarity, and adherence to constraints, making it the preferred solution for both interviews and production code where integer-only manipulation is required.