Problem Description

Given an integer x, you need to determine whether it is a palindrome. A palindrome integer reads the same backward as forward. Return true if x is a palindrome, and false otherwise.

For example:

• 121 is a palindrome because it reads the same from left to right and right to left
• -121 is not a palindrome because from left to right it reads -121, but from right to left it becomes 121-
• 10 is not a palindrome because from right to left it becomes 01

The solution uses a clever approach of reversing only half of the number instead of converting it to a string. It handles special cases first:

• Negative numbers are never palindromes due to the minus sign
• Numbers ending in 0 (except 0 itself) cannot be palindromes since they would need to start with 0

The algorithm then reverses the second half of the number digit by digit. It extracts the last digit using x % 10 and builds the reversed number y by multiplying y by 10 and adding the extracted digit. The original number x is reduced by dividing by 10.

The process continues until the reversed portion y becomes greater than or equal to the remaining portion of x. At this point, if the number is a palindrome, either:

• x equals y (for even-length numbers like 1221 → comparing 12 with 12)
• x equals y // 10 (for odd-length numbers like 12321 → comparing 12 with 123, where we ignore the middle digit)

Intuition

The most straightforward approach would be to convert the integer to a string and check if it reads the same forwards and backwards. However, this requires extra space for string conversion.

To solve this without string conversion, we need to think about what makes a number a palindrome. A palindrome has symmetry - the first half mirrors the second half. This observation leads us to consider: what if we could extract and reverse just half of the number, then compare it with the other half?

Consider the number 1221. If we can somehow get the last two digits 21, reverse them to get 12, and compare with the first two digits 12, we'd know it's a palindrome.

The key insight is that we can extract digits from the end of a number using the modulo operator %. For any number, x % 10 gives us the last digit. After extracting a digit, we can remove it by integer division x // 10.

But how do we know when we've reversed exactly half? Here's the clever part: as we build the reversed number y by repeatedly taking digits from x, the reversed portion grows while the original shrinks. When y becomes greater than or equal to x, we know we've processed at least half the digits.

For even-length palindromes like 1221, after processing half the digits, x and y will be equal (12 and 12). For odd-length palindromes like 12321, the reversed half will be one digit longer (123 vs 12), but if we divide y by 10 to remove the middle digit, they should match.

The edge cases become clear when thinking about the reversal process:

• Negative numbers have a - sign that breaks symmetry
• Numbers ending in 0 would need to start with 0 after reversal, which isn't valid for positive integers (except 0 itself)

Learn more about Math patterns.

Solution Approach

The implementation follows the strategy of reversing half of the number and comparing it with the first half.

Step 1: Handle Special Cases

First, we check for cases where the number cannot be a palindrome:

• If x < 0, return false immediately since negative numbers have a minus sign
• If x > 0 and x % 10 == 0, return false since numbers ending in 0 (except 0 itself) cannot be palindromes

The condition x and x % 10 == 0 ensures we only reject positive numbers ending in 0, not 0 itself.

Step 2: Reverse the Second Half

We initialize y = 0 to store the reversed half. Then we enter a loop that continues while y < x:

1. Extract the last digit of x using x % 10
2. Append this digit to y by calculating y = y * 10 + x % 10
3. Remove the last digit from x using integer division x //= 10

For example, with x = 1221:

• Initially: x = 1221, y = 0
• First iteration: y = 0 * 10 + 1 = 1, x = 122
• Second iteration: y = 1 * 10 + 2 = 12, x = 12
• Loop ends since y >= x

Step 3: Compare the Halves

After the loop, we need to handle two cases:

• Even-length palindrome: The two halves have equal length. For 1221, we get x = 12 and y = 12. They should be equal.

• Odd-length palindrome: The reversed half has one extra digit (the middle digit). For 12321, we get x = 12 and y = 123. We need to compare x with y // 10 (which removes the middle digit from y).

The final return statement return x in (y, y // 10) elegantly handles both cases by checking if x equals either y or y // 10.

Time and Space Complexity

• Time Complexity: O(log n) where n is the input number, since we process roughly half of the digits
• Space Complexity: O(1) as we only use a constant amount of extra space

Example Walkthrough

Let's walk through the algorithm with the number 12321:

Step 1: Check Special Cases

• Is x = 12321 negative? No, so we continue.
• Does it end in 0? 12321 % 10 = 1, so no. We proceed to the main algorithm.

Step 2: Reverse the Second Half

We start with x = 12321 and y = 0. Now we'll extract digits from the end of x and build y:

• Iteration 1:

  • Extract last digit: 12321 % 10 = 1
  • Build reversed number: y = 0 * 10 + 1 = 1
  • Remove last digit from x: x = 12321 // 10 = 1232
  • Check condition: y = 1 < x = 1232, continue

• Iteration 2:

  • Extract last digit: 1232 % 10 = 2
  • Build reversed number: y = 1 * 10 + 2 = 12
  • Remove last digit from x: x = 1232 // 10 = 123
  • Check condition: y = 12 < x = 123, continue

• Iteration 3:

  • Extract last digit: 123 % 10 = 3
  • Build reversed number: y = 12 * 10 + 3 = 123
  • Remove last digit from x: x = 123 // 10 = 12
  • Check condition: y = 123 >= x = 12, stop

Step 3: Compare the Halves

Now we have x = 12 and y = 123.

Since this is an odd-length number, we've reversed one digit more than half (the middle digit 3 is included in y). We check:

• Is x == y? No, 12 ≠ 123
• Is x == y // 10? Yes! 12 == 123 // 10 = 12

Since one condition is satisfied, we return true. The number 12321 is indeed a palindrome!

For contrast, let's quickly see what happens with a non-palindrome like 123:

• After reversal: x = 1, y = 32
• Check: 1 ≠ 32 and 1 ≠ 32 // 10 = 3
• Return false

Solution Implementation

Time and Space Complexity

The time complexity is O(log₁₀(n)), where n is the input integer x. The algorithm reverses half of the digits by repeatedly extracting the last digit of x using modulo operation (x % 10) and dividing x by 10 (x //= 10). Since we process approximately half of the digits (the loop continues while y < x), and the number of digits in n is ⌊log₁₀(n)⌋ + 1, the total number of iterations is proportional to log₁₀(n).

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store the variable y (the reversed half of the number), regardless of the input size. No additional data structures or recursive calls are used that would scale with the input.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Special Case Handling for Zero

Pitfall: A common mistake is writing the condition as if x < 0 or x % 10 == 0: instead of if x < 0 or (x != 0 and x % 10 == 0):. This would incorrectly classify 0 as not a palindrome, when 0 is actually a valid single-digit palindrome.

Solution: Always explicitly check x != 0 before rejecting numbers ending in 0:

# Correct
if x < 0 or (x != 0 and x % 10 == 0):
    return False

# Incorrect - would reject 0 as a palindrome
if x < 0 or x % 10 == 0:
    return False

2. Loop Termination Condition Error

Pitfall: Using while x > 0 or while x >= reversed_half as the loop condition instead of while reversed_half < x. This causes the algorithm to reverse the entire number rather than just half, defeating the optimization purpose and potentially causing incorrect results.

Solution: The loop should continue only while the reversed portion is smaller than the remaining original number:

# Correct - stops when we've reversed approximately half
while reversed_half < x:
    reversed_half = reversed_half * 10 + x % 10
    x //= 10

# Incorrect - reverses the entire number
while x > 0:
    reversed_half = reversed_half * 10 + x % 10
    x //= 10

3. Integer Overflow in Other Languages

Pitfall: While Python handles arbitrary precision integers automatically, in languages like Java or C++, building reversed_half could cause integer overflow for large palindromes near the maximum integer value.

Solution: In languages with fixed integer sizes, either:

• Use a long/long long type for reversed_half
• Add overflow checking before the multiplication
• Consider the string conversion approach for very large numbers

4. Forgetting the Odd-Length Case

Pitfall: Only checking x == reversed_half without considering x == reversed_half // 10. This would incorrectly classify odd-length palindromes like 121 or 12321 as non-palindromes.

Solution: Always include both checks in the return statement:

# Correct - handles both even and odd length palindromes
return x == reversed_half or x == reversed_half // 10

# Incorrect - only works for even-length palindromes
return x == reversed_half

5. Modifying Input Before Special Case Check

Pitfall: Starting to reverse digits before checking if the number ends in 0, which could lead to unnecessary computation or incorrect results.

Solution: Always perform special case validation before entering the main algorithm:

# Correct order
if x < 0 or (x != 0 and x % 10 == 0):
    return False
# Then start the reversal process

# Incorrect - wastes computation or may give wrong results
reversed_half = 0
while reversed_half < x:
    # ... reversal logic
# Then checking special cases (too late!)