Reverse Integer

Reversing digits is easy. Reversing them without ever creating an unsafe intermediate value is the interview problem.

Start with the contract

You receive a signed 32-bit integer x. Return its decimal digits in reverse order. If the reversed value falls outside:

[-2^31, 2^31 - 1]
= [-2147483648, 2147483647]

return 0.

The input itself is already inside that range, but its reversal may not be. For example:

123        → 321
-123       → -321
120        → 21
2147483647 → 7463847412 → 0

The last case exposes the real constraint. A weak implementation builds the entire reversed value and checks the bounds afterward. In a fixed-width environment, that may be too late:

next_result = result * 10 + digit

The multiplication or addition can overflow before the program gets a chance to compare next_result with the limit.

The correct direction is:

1. Extract one digit from the remaining input.
2. Check whether appending that digit would stay in range.
3. Commit the update only after the check passes.

The check belongs before the arithmetic.

Recognize the state-tracking pattern

The digits arrive in the opposite order from the one we need:

• x % 10 gives the rightmost unprocessed digit.
• The answer is built from left to right.
• Each iteration consumes exactly one digit.
• Everything learned from previous iterations can be summarized by one running result.

That is a compact state-tracking problem. We do not need a window, a map, a recursive recurrence, or a greedy choice. We need two pieces of evolving state:

• remaining: the digits that have not been consumed yet.
• result: the reversed prefix already committed.

A string conversion is a reasonable baseline:

str(x)[::-1]

But it avoids the arithmetic mechanism this problem is testing. It also leaves overflow detection to string parsing or to a later conversion. For an interview, I would use the string idea only to confirm the expected behavior, then switch to arithmetic digit extraction.

The stronger mental model is a small conveyor belt: remove one digit from the right, inspect the load already built, then append the new digit if the next state is safe.

Derive the digit transition

For a nonnegative number, the last decimal digit is:

digit = remaining % 10

Removing that digit is:

remaining //= 10

The reversed prefix grows through:

result = result * 10 + digit

Why does this work? Multiplying by 10 shifts every existing digit one decimal place to the left. Adding digit places the newly extracted digit at the end.

For 123:

Remaining input	Extracted digit	Result
123	3	3
12	2	32
1	1	321
0	—	321

For 120:

Remaining input	Extracted digit	Result
120	0	0
12	2	2
1	1	21

The first extracted zero does not need special cleanup. It becomes a leading zero in the mathematical construction, and integer representation drops it naturally:

0 → 2 → 21

Handle the sign separately in Python

A clean Python implementation records the sign and processes the magnitude:

sign = -1 if x < 0 else 1
remaining = abs(x)

Then it reverses the nonnegative magnitude and applies the sign at the end.

This also avoids a Python-specific trap. In Python, // is floor division, not truncation toward zero:

-123 // 10  # -13

But removing the last digit from -123 using truncation toward zero should produce -12, not -13. Processing abs(x) means // behaves exactly as needed for the magnitude.

The minimum 32-bit integer deserves special attention:

-2^31 = -2147483648

Its magnitude is 2147483648, one larger than the positive maximum. Python can represent that magnitude, so the code can process it directly. In a fixed-width language, taking the absolute value of the minimum integer may itself be unsafe; that implementation must preserve the sign or use signed-boundary checks directly.

Derive the pre-update overflow check

The dangerous transition is:

next_result = result * 10 + digit

We need to prove that next_result will fit before evaluating it.

With sign separated, result and digit are nonnegative. The permitted magnitude depends on the original sign:

• Positive result: maximum magnitude is 2147483647.
• Negative result: maximum magnitude is 2147483648, because -2147483648 is valid.

Call this magnitude limit limit.

The question becomes:

result * 10 + digit <= limit

Instead of calculating the left side first, divide the limit into its quotient and final digit:

limit = (limit // 10) * 10 + (limit % 10)

Therefore, the next update is unsafe when:

result > limit // 10

because multiplying the prefix by 10 already exceeds the limit.

If the prefix is exactly at the boundary:

result == limit // 10

then the new digit decides whether the update fits:

digit > limit % 10

So the complete guard is:

if result > limit // 10:
    return 0

if result == limit // 10 and digit > limit % 10:
    return 0

For the positive boundary:

limit = 2147483647
limit // 10 = 214748364
limit % 10 = 7

The final digit may be at most 7.

For the negative boundary, we use the magnitude:

limit = 2147483648
limit // 10 = 214748364
limit % 10 = 8

The final magnitude digit may be at most 8. That asymmetry is the detail many otherwise-correct solutions miss.

Current magnitude prefix	Next digit	Decision
Greater than limit // 10	Any	Reject
Equal to limit // 10	Greater than limit % 10	Reject
Equal to limit // 10	At most limit % 10	Safe
Less than limit // 10	Any digit	Safe

This is the required 32 bit overflow check: validate the next state from the current state, rather than creating an oversized temporary and inspecting the damage afterward.

Python integers have arbitrary precision, so Python itself will not overflow during result * 10 + digit. That does not remove the obligation. The problem explicitly asks us to model a signed 32-bit result without relying on a wider integer type. The guard keeps the algorithm faithful to that contract and portable to fixed-width languages.

State the invariant

A correct loop needs more than a plausible transition. It needs a statement that remains true after every iteration.

After each iteration, result is the reversal of the digits already removed from the original magnitude, and remaining contains exactly the digits not yet processed.

Initially, no digits have been removed:

result = 0
remaining = abs(x)

The invariant holds.

During an iteration:

1. digit = remaining % 10 extracts the next unprocessed digit.
2. remaining //= 10 removes it.
3. result * 10 + digit shifts the committed reversed prefix and appends the extracted digit.

If the guard passes, the new result is both the correct reversal of the processed digits and still within the permitted magnitude. If the guard fails, no invalid update is performed, and returning 0 matches the problem contract.

The loop terminates because every iteration removes one decimal digit from remaining. Zero and one-digit inputs need no special branch:

• If x == 0, the loop never runs and the result is 0.
• If x == 7, one digit is extracted and the result is 7.
• If x == 120, the extracted zero is handled by the same transition as every other digit.

Termination plus the invariant gives the result. The guard gives safety. That is the whole proof structure.

Trace the cases that expose bugs

Basic examples confirm digit order, but boundary tests confirm the reasoning.

Positive and negative values

For 123:

result: 0 → 3 → 32 → 321
return: 321

For -123, the magnitude follows the same path:

magnitude result: 0 → 3 → 32 → 321
apply sign: -321

The sign does not interfere with digit extraction.

Trailing zeroes

For 120:

digit 0: result = 0
digit 2: result = 2
digit 1: result = 21

The result is 21. Do not add a string-trimming step or a special case for zero. The arithmetic already gives the correct integer representation.

Zero and one digit

These are useful termination tests:

0 → 0
5 → 5
-8 → -8

A loop that handles only multi-digit values often reveals itself here through an incorrect initialization or an unnecessary sign branch.

Both signed limits

The input can be valid while its reversed output is invalid:

2147483647 → 7463847412 → 0
-2147483648 → -8463847412 → 0

Test both. The negative limit is not merely the positive limit with a minus sign; its magnitude ends in 8, not 7.

A valid value near a boundary

It is equally important to test a reversal that remains valid. For example:

1463847412 → 2147483641

This result is below 2147483647, so it must be returned rather than rejected. Boundary logic should distinguish “close to the limit” from “outside the limit.”

A useful test set is organized by proof obligation:

Obligation	Example
Digit extraction	123 → 321
Sign preservation	-123 → -321
Leading-zero removal	120 → 21
Zero handling	0 → 0
One-digit identity	7 → 7
Positive overflow	2147483647 → 0
Negative underflow	-2147483648 → 0
Valid boundary-near result	1463847412 → 2147483641

Implement the Reverse Integer solution in Python

The implementation below keeps the state visible:

• sign preserves the original sign.
• remaining stores unprocessed magnitude digits.
• result stores the reversed magnitude prefix.
• limit encodes the correct boundary for that sign.

class Solution:
    def reverse(self, x: int) -> int:
        MIN_INT = -(2**31)
        MAX_INT = 2**31 - 1

        sign = -1 if x < 0 else 1
        remaining = abs(x)

        # Negative values may use the extra magnitude represented by MIN_INT.
        limit = MAX_INT if sign == 1 else -MIN_INT

        result = 0

        while remaining:
            digit = remaining % 10
            remaining //= 10

            # Check result * 10 + digit before performing the update.
            if result > limit // 10:
                return 0

            if result == limit // 10 and digit > limit % 10:
                return 0

            result = result * 10 + digit

        return sign * result

For a positive result, the boundary test is effectively:

result < 214748364
result == 214748364 and digit <= 7

For a negative result, the magnitude test allows:

result == 214748364 and digit <= 8

That is why the code derives limit from sign instead of hard-coding one final digit.

The code also never computes an out-of-range candidate and then asks whether it was valid. It proves the transition safe first, then commits it. That ordering is the important part.

Complexity and common mistakes

If x has d decimal digits, the loop runs exactly d times. Since d is proportional to log |x|, the complexity is:

Time:  O(log |x|)
Space: O(1)

The algorithm stores only a few integer variables regardless of the number of digits.

Watch for these failure modes:

1. Checking overflow after the update
   result = result * 10 + digit may already be invalid in a fixed-width type.

2. Using one limit for both signs
   Positive values stop at 2147483647; negative magnitudes may reach 2147483648.

3. Using // directly on a negative Python input
   Python floors negative division. Process the magnitude or implement truncation toward zero explicitly.

4. Assuming a valid input guarantees a valid reversal
   Both signed input limits reverse outside the permitted range.

5. Using strings when arithmetic is the point
   String reversal can produce the expected output, but it does not demonstrate digit extraction or pre-update safety.

The reusable rule is simple:

Whenever a running numeric state is updated as state * base + piece, validate the next transition before executing it.

In an interview, make the reasoning visible:

1. Name the smallest evolving state.
2. Write the transition.
3. State the invariant.
4. Derive the boundary that makes the transition safe.
5. Test the ordinary path and the boundary path.

Read the state. Guard the transition. Then commit the update. That workflow scales well beyond integer digit reversal.