Palindrome Number: Half-Reversal Without String Conversion

LeetCode 9. Palindrome Number asks you to determine whether an integer reads the same forward and backward. Negative numbers are never palindromes. The follow-up challenge: solve it without converting the integer to a string.

The key insight is that you do not need to reverse the entire number. You only need to reverse half of it and compare.

Problem statement

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

• 121 is a palindrome (reads the same forward and backward)
• -121 is not a palindrome (the leading - means it reads differently backward)
• 10 is not a palindrome (01 is not the same as 10)

Approach 1: String conversion (simple baseline)

The most direct way to check is to convert the number to a string and compare it to its reverse.

def is_palindrome(x: int) -> bool:
    s = str(x)
    return s == s[::-1]

This works and passes on LeetCode. It runs in O(log n) time (the number of digits is proportional to log base 10 of n) and O(log n) space for the string. But the problem explicitly asks you to solve it without string conversion, and interviewers often want to see the math-based approach.

Approach 2: Half-reversal (no string conversion)

Instead of converting to a string, you can reverse the second half of the number's digits and compare it to the first half. The algorithm works as follows:

1. Reject negative numbers and numbers ending in 0 (except 0 itself) immediately.
2. Build a reversed_half by repeatedly extracting the last digit of x and appending it to reversed_half.
3. Stop when reversed_half is greater than or equal to x. At that point, you have reversed half the digits.
4. For even-length numbers, x == reversed_half means palindrome. For odd-length numbers, x == reversed_half // 10 means palindrome (the middle digit ends up in reversed_half and can be discarded).

def is_palindrome(x: int) -> bool:
    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 //= 10

    return x == reversed_half or x == reversed_half // 10

This approach avoids creating any string. It also avoids reversing the full number, which sidesteps potential integer overflow in languages with fixed-width integers (not a concern in Python, but important in C++ or Java).

Visual walkthrough: x = 1221

Let's trace through the half-reversal approach step by step.

After two iterations, x and reversed_half are both 12. Since x == reversed_half, the number is a palindrome. For an odd-length number like 12321, you would end up with x = 12 and reversed_half = 123, and the check x == reversed_half // 10 handles discarding the middle digit.

Why stop at half?

Reversing only half the number is more than an optimization. In languages like Java or C++, reversing the full number can overflow if the input is near the maximum integer value. By stopping at the midpoint, the reversed portion never exceeds the original, so overflow is impossible. In Python, integers have arbitrary precision, so overflow is not a practical concern. But the half-reversal approach is still worth knowing because interviewers expect it and it transfers directly to other languages.

Complexity analysis

The string approach uses O(log n) space for the string allocation. The half-reversal approach brings that down to O(1).

Building blocks

This problem decomposes into two reusable pieces that appear in many other LeetCode problems.

1. Digit extraction with modular arithmetic

Pulling the last digit off a number using x % 10 and then removing it with x //= 10. This is the same micro-pattern used in Happy Number, Reverse Integer, and Add Digits.

while x > 0:
    digit = x % 10
    x //= 10

2. Half-reversal pattern

Building a reversed number from extracted digits and stopping when the reversed portion catches up to the remaining portion. This avoids full reversal, prevents overflow, and naturally handles both even-length and odd-length inputs with a single extra check (reversed_half // 10).

reversed_half = 0
while x > reversed_half:
    reversed_half = reversed_half * 10 + x % 10
    x //= 10

On CodeBricks, you drill each building block separately so that when they appear together in a problem like this, you recognize both pieces instantly.

Edge cases

• Negative numbers: Always return false. The minus sign means the number cannot read the same in both directions.
• Single-digit numbers (0 through 9): Always palindromes. The while loop condition x > reversed_half is immediately false, and the check x == reversed_half passes since both are equal to the original number.
• Trailing zeros: A number like 10 or 120 ends in zero but does not start with zero. You catch these early with x % 10 == 0 and x != 0. Without this guard, the algorithm would incorrectly match x = 0 with reversed_half = 01 (which is just 1).
• Zero itself: Handled by the x != 0 exception in the trailing-zero check. Zero is a palindrome.

From understanding to recall

You can read through this solution in a few minutes and understand every line. But understanding is not the same as being able to reproduce it under interview pressure two weeks from now.

The gap between understanding and recall is where spaced repetition comes in. CodeBricks breaks Palindrome Number into its building blocks (digit extraction with mod/div, half-reversal with a stopping condition) and drills them at increasing intervals. You type each piece from scratch, building real muscle memory. After a few review cycles, the half-reversal pattern becomes automatic rather than something you have to rederive.

Related posts

• Valid Palindrome - Two-pointer palindrome check on strings, the string counterpart to this number-based problem
• Reverse Linked List - Reversing a linked list in place, another problem where working with half the structure (as in Palindrome Linked List) uses a similar idea