Palindrome Number

A full reverse is easy to write. The interview-level move is to stop reversing when the two halves meet.

For a no-string Palindrome Number solution, reject impossible representations first, reverse only the lower half with digit arithmetic, then compare the two halves at the midpoint. This keeps the state small and avoids constructing a complete reversed integer.

The contract and the answer direction

Return True exactly when the ordinary decimal representation of x reads identically from left to right and right to left.

A few representation rules determine the early exits:

• A negative number is not a palindrome because the minus sign has no matching sign on the other side.
• A positive number ending in 0 is not a palindrome. Its reverse would need a leading zero, but ordinary decimal notation does not include that zero.
• 0 is a palindrome because its one-digit representation is already symmetric.

The input range is bounded by:

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

The straightforward method is to reverse every digit and compare the result with the original. That gives us a useful correctness baseline. But the no-string follow-up points toward a better state representation:

1. Reject negative values and nonzero trailing zeroes.
2. Consume digits from the right.
3. Build only the reversed lower half.
4. Stop when that half reaches the remaining upper half.
5. Compare directly, or remove the unmatched middle digit for odd-length numbers.

The key idea is simple: do not build information you will never need.

Read the representation, not the label

This problem is about symmetry in a fixed decimal representation. It is not asking for a longest palindrome, a substring range, or a two-dimensional search. The output is only a boolean: does the representation mirror itself?

That recognition matters because it narrows the state we need.

Imagine the number as two regions meeting at a center:

upper half | lower half

The lower half is easiest to consume because decimal arithmetic exposes the rightmost digit:

• x % 10 extracts the last digit.
• x // 10 removes the last digit.

As we consume the lower half, we reverse it into a second value. At the same time, the remaining value shrinks from the right. Eventually, the reversed lower half meets the unprocessed upper half.

Those two evolving values are enough:

• remaining: the digits still unconsumed from the original prefix.
• reversed_half: the consumed suffix, written in reverse order.

This is state tracking in its smallest useful form. We preserve exactly what the midpoint comparison needs—no string, array, or full reverse.

Baseline: reverse every digit

Before optimizing, derive the basic digit operations.

Suppose the current value is 12321.

1. 12321 % 10 gives 1.
2. 12321 // 10 gives 1232.
3. Append the extracted digit with:

reversed_value = reversed_value * 10 + digit

The accumulator changes like this:

0   -> 1   -> 12   -> 123   -> 12321

A full-reversal baseline in Python looks like this:

def is_palindrome_full(x: int) -> bool:
    if x < 0:
        return False

    original = x
    reversed_value = 0

    while x > 0:
        digit = x % 10
        reversed_value = reversed_value * 10 + digit
        x //= 10

    return original == reversed_value

This is a useful first implementation and debugging reference. It makes the digit mechanics visible.

However, building the complete reverse creates a fixed-width risk. In languages with bounded integer types, the reversed value can overflow while it is being constructed, even when the final comparison would have been enough to reject the number. Python integers handle large values differently, but the half-reversal method still answers the intended constraint more directly: no string conversion and no unnecessary full reverse.

Derive the half-reversal state

Start with a positive number after the early rejection checks:

remaining = x
reversed_half = 0

Each iteration moves one digit from remaining into reversed_half:

digit = remaining % 10
reversed_half = reversed_half * 10 + digit
remaining //= 10

The invariant is the important part:

After every iteration, reversed_half is the reverse of the original suffix already consumed, and remaining is the original prefix that has not been consumed yet.

For 1221, the state evolves as follows:

The two values now meet:

remaining       = 12
reversed_half   = 12

That is the even-length case.

For 12321:

The reversed half has passed the remaining prefix because the middle digit was consumed. The extra 3 belongs to neither side of the final comparison, so it must be removed:

reversed_half // 10 == 12

Why stop at reversed_half >= remaining?

Before the loop begins, reversed_half has no digits and remaining has all the digits. Each iteration adds one digit to the reversed side and removes one digit from the remaining side.

The two values therefore approach the center from opposite directions. Once:

reversed_half >= remaining

the lower half has reached or crossed the midpoint. Continuing would consume digits that are not needed for the symmetry test and could make the state harder to reason about.

This is the stopping boundary we want. It does not depend on calculating the number of digits first, and it works for both even and odd lengths.

Prove the final comparison

At the midpoint, there are two possible shapes.

Even number of digits

For 1221, the state is:

remaining = 12
reversed_half = 12

The lower half was 21. Reversing it produces 12, which must equal the upper half for the number to be a palindrome.

So the condition is:

remaining == reversed_half

Odd number of digits

For 12321, the state is:

remaining = 12
reversed_half = 123

The final digit of reversed_half is the unmatched middle digit. Remove it with integer division:

reversed_half // 10 == remaining

The complete final condition is therefore:

remaining == reversed_half or remaining == reversed_half // 10

Why is this sufficient? Every digit removed from the original suffix appears in reversed_half in the order needed for comparison with the prefix. If a mirrored pair differs, that difference remains in one of the two final half-values. Removing only the odd-length middle digit cannot erase a mismatch between mirrored positions.

The early rejection checks are part of the same proof:

• A negative value contains a sign that cannot mirror a digit.
• A positive value ending in zero would need a leading zero after reversal, which ordinary decimal representation does not supply.

Implement the Python solution

Here is the compact no-string implementation:

def is_palindrome(x: int) -> bool:
    # Negative numbers have a minus sign, so they cannot be palindromes.
    # A positive number ending in zero would need a leading zero when reversed.
    if x < 0 or (x % 10 == 0 and x != 0):
        return False

    reversed_half = 0

    # The two tracked sides meet at the midpoint.
    while reversed_half < x:
        digit = x % 10
        reversed_half = reversed_half * 10 + digit
        x //= 10

    # Even length: x == reversed_half
    # Odd length: discard the middle digit from reversed_half.
    return x == reversed_half or x == reversed_half // 10

The parameter x is deliberately reused as the remaining prefix. We do not need the original value after the midpoint because the two evolving states contain the information required for the decision.

The loop guard is also doing more work than it first appears:

while reversed_half < x:

It guarantees that we stop once the reversed suffix reaches the remaining prefix. The final or handles the two parity cases without requiring a separate digit count.

In a fixed-width language, the same state design avoids constructing a full reversed value. The important property is not the syntax of Python; it is that reversed_half grows only until the midpoint.

Test the boundaries and failure modes

Good tests should attack the representation boundaries, not just confirm the happy path.

Zero

x = 0

The loop does not run because reversed_half < x is 0 < 0, which is false. The final comparison is:

0 == 0

So the result is True.

Zero must be handled explicitly in the trailing-zero check. The rule is “a nonzero number ending in zero fails,” not “every number ending in zero fails.”

Negative input

x = -121

The function returns False immediately. The digits 121 are symmetric, but the actual representation includes -, so the full representation is not mirrored.

Trailing zero

x = 10

The function returns False before reversal. Normal decimal notation represents this as 10, not 010; its reverse would require a leading zero that is not part of the representation.

This is a common failure mode in solutions that reverse digits mechanically but do not define what representation they are checking.

Odd digit count

x = 121

The state changes like this:

remaining = 121, reversed_half = 0
remaining = 12,  reversed_half = 1
remaining = 1,   reversed_half = 12

Now the halves have crossed. The middle digit is the final 2 in reversed_half, so compare:

1 == 12 // 10

That is True.

Even digit count

x = 1221

After two iterations:

remaining = 12
reversed_half = 12

The direct comparison succeeds.

Non-palindrome

x = 1234

The state reaches:

remaining = 12
reversed_half = 43

Neither comparison succeeds:

12 != 43
12 != 43 // 10

The algorithm rejects the value without ever constructing 4321.

The supplied 32-bit range makes the method safe in fixed-width implementations when the reversed state is limited to half the digits. The broader lesson is more useful than the particular bound: stop accumulating state when the decision boundary has been reached.

Complexity and the reusable rule

A decimal integer with d digits is divided by 10 once per loop iteration, and the loop processes roughly half of those digits. The time complexity is:

O(log10 |x|)

This is proportional to the number of decimal digits. The algorithm stores only x and reversed_half, so its auxiliary space is:

O(1)

The reusable interview rule is this:

When a fixed representation has mirrored structure and the output is a symmetry check, ask whether one side can be consumed while preserving exactly enough state to meet the other at the midpoint.

Do not memorize the final or condition in isolation. Derive it from the invariant:

1. Reject representations that cannot be symmetric.
2. Define what each state variable means.
3. Consume digits from one side.
4. Prove why the loop stops at the center.
5. Handle even and odd centers separately.
6. Test zero, negative values, trailing zeroes, and both digit parities.

Track the state. Find the boundary. Let the comparison fall out of the invariant.