LeetCode 7 – Reverse Integer

Reverse Integer is tagged Easy and it is not, quite. Reversing the digits takes four lines. The problem is the sentence at the bottom: if the reversed value falls outside the 32-bit signed range, return 0 — and you are not allowed to store a 64-bit number to find out.

The problem

Given a signed 32-bit integer, reverse its digits. If reversing causes the value to fall outside [-2³¹, 2³¹ - 1], return 0. Assume the environment cannot store 64-bit integers.

Input:  123           Output:  321
Input:  -123          Output: -321        the sign survives
Input:  120           Output:  21         trailing zeros just disappear
Input:  1534236469    Output:  0          reversed it would be 9646324351, past 2³¹ - 1

The two-line core

x % 10 peels off the last digit, x / 10 drops it. Repeat until nothing is left, and each peeled digit gets shifted into place with result = result * 10 + digit.

In Java the sign takes care of itself, and this is worth understanding rather than memorising. Java's % truncates toward zero, so -123 % 10 is -3, not 7. Feed negative digits into a negative accumulator and you get a negative reversal for free — no Math.abs, no sign variable, and no separate Integer.MIN_VALUE special case (which Math.abs could not have represented anyway).

Trailing zeros need no handling either. Reversing 120 starts with result = 0 * 10 + 0, which is still 0, and the leading zero simply never exists.

The overflow check without a wider type

The interesting part. result * 10 + digit may overflow, and in Java signed overflow wraps silently — no exception, just a wrong answer. Two ways to catch it:

Check afterwards, by undoing the step. If (next - digit) / 10 does not land back on result, the multiplication wrapped. This reads oddly but it is short and it never needs a wider type:

int next = result * 10 + digit;
if ((next - digit) / 10 != result) return 0;   // the multiply wrapped

Check beforehand, by rearranging the inequality. Overflow means result * 10 + digit > Integer.MAX_VALUE. Divide through by 10 and it becomes a comparison that itself cannot overflow — this is the version to prefer, because it relies on arithmetic that stayed in range rather than on inspecting damage after the fact:

if (result > (Integer.MAX_VALUE - digit) / 10) return 0;

Java

class Solution {
    public int reverse(int x) {
        int result = 0;

        while (x != 0) {
            int digit = x % 10;   // truncates toward zero, so the sign rides along
            x /= 10;

            // Undo the step. If it does not land back on result, the multiply wrapped.
            int next = result * 10 + digit;
            if ((next - digit) / 10 != result) {
                return 0;
            }
            result = next;
        }

        return result;
    }
}

Python

Python needs the opposite care. Its integers are arbitrary precision, so nothing ever overflows and the range check has to be applied by hand at the end. Its % also floors rather than truncating — -123 % 10 is 7, not -3 — so the digit-peeling trick does not carry the sign the way Java's does. Split the sign off first:

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

        sign = -1 if x < 0 else 1
        x = abs(x)                     # Python's % floors, so strip the sign first

        result = 0
        while x:
            x, digit = divmod(x, 10)
            result = result * 10 + digit

        result *= sign
        return result if INT_MIN <= result <= INT_MAX else 0

Complexity

O(log₁₀ x) time — one iteration per digit, so at most 10 for a 32-bit integer. O(1) space. Calling it O(1) outright is fair given the fixed width, and saying "constant, because a 32-bit integer has at most ten digits" shows you know why.

The string solution, and when to mention it

Converting to a string, reversing it, and parsing it back works and is one line in Python. It costs O(n) extra space and it moves the overflow problem into Integer.parseInt, which throws instead of returning 0. Mention it as the obvious approach, then explain why you are doing the arithmetic instead — that comparison is half of what the question is testing.

What the interviewer is checking

• That you detect overflow without promoting to long. Reaching for a long is the first thing to try and the problem explicitly forbids it.
• That negatives work — and that you can explain why they need no extra code in Java.
• That Integer.MIN_VALUE does not blow up. Its absolute value is not a valid int, so any solution built on Math.abs is already broken.
• That trailing zeros need no handling, and that you know why.