LeetCode 7: Reverse Integer

Problem Restatement

We are given a signed 32-bit integer x.

We need to reverse its digits.

Examples:

123 -> 321
-123 -> -321
120 -> 21

If the reversed value goes outside the signed 32-bit integer range, we return 0.

The valid range is:

[-2^31, 2^31 - 1]

which means:

[-2147483648, 2147483647]

The official problem also says to assume the environment does not allow storing 64-bit integers.

Input and Output

Example function shape:

def reverse(x: int) -> int:
    ...

Examples

Example 1:

x = 123

Reverse the digits:

321

Output:

321

Example 2:

x = -123

Reverse the digits and keep the negative sign:

-321

Output:

-321

Example 3:

x = 120

Reverse the digits:

021

Leading zeroes disappear in an integer, so the result is:

21

Output:

21

Example 4:

x = 1534236469

The reversed value would be:

9646324351

This is larger than 2147483647, so the answer is:

0

First Thought: Convert to String

A simple Python solution is:

class Solution:
    def reverse(self, x: int) -> int:
        sign = -1 if x < 0 else 1
        value = abs(x)

        reversed_value = int(str(value)[::-1]) * sign

        if reversed_value < -2**31 or reversed_value > 2**31 - 1:
            return 0

        return reversed_value

This is short and works in Python.

But it does not respect the spirit of the problem. The statement asks us to assume we cannot store 64-bit integers. So we should solve it using digit operations and check overflow before it happens.

Key Insight

To reverse a number numerically, repeatedly take the last digit from x and append it to the result.

For example:

x = 123
result = 0

Take last digit:

digit = 3
result = 0 * 10 + 3 = 3
x = 12

Take next digit:

digit = 2
result = 3 * 10 + 2 = 32
x = 1

Take next digit:

digit = 1
result = 32 * 10 + 1 = 321
x = 0

Now return:

321

The only difficult part is overflow.

Before doing:

result = result * 10 + digit

we must check whether that operation would leave the 32-bit signed range.

Overflow Check

The maximum allowed value is:

MAX_INT = 2**31 - 1

The minimum allowed value is:

MIN_INT = -2**31

Before appending a digit, we check:

result > MAX_INT // 10

If this is true, multiplying by 10 will overflow.

If:

result == MAX_INT // 10

then the final digit must be at most 7, because:

MAX_INT = 2147483647

For the negative side, the last allowed digit is 8, because:

MIN_INT = -2147483648

To keep the code simple in Python, we can process the absolute value and restore the sign at the end. Then we only need to check against 2147483647 for positive inputs and 2147483648 for negative inputs.

Algorithm

1. Store the sign.
2. Work with the absolute value of x.
3. Set result = 0.
4. Set limit:
   • 2147483647 for positive results
   • 2147483648 for negative results
5. While the number is not zero:
   • take the last digit
   • remove the last digit from the number
   • check whether appending the digit would overflow
   • append the digit
6. Return sign * result.

Correctness

The algorithm removes digits from the original number from right to left.

Each removed digit is appended to the right side of result.

After processing the first k digits, result contains exactly those k digits in reversed order.

This gives a simple invariant:

result is the reverse of the digits already removed from x

At each step, appending the next last digit preserves this invariant.

When x becomes 0, all digits have been removed and appended to result.

So result is the full digit reversal of the original absolute value.

The sign is stored separately, so the final sign matches the input.

Before every append operation, the algorithm checks whether:

result * 10 + digit

would exceed the allowed bound.

If it would exceed the bound, the function returns 0, exactly as required.

Therefore the algorithm returns the reversed integer when it is valid, and returns 0 when the reversed integer overflows.

Complexity

For a 32-bit integer, the number of digits is bounded, so this is effectively constant time. But in general digit terms, it is logarithmic in the input value.

Implementation

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

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

        limit = MAX_NEGATIVE_ABS if sign == -1 else MAX_POSITIVE

        result = 0

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

            if result > limit // 10:
                return 0

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

            result = result * 10 + digit

        return sign * result

Code Explanation

We define the positive and negative bounds:

MAX_POSITIVE = 2**31 - 1
MAX_NEGATIVE_ABS = 2**31

For a negative result, the absolute value may reach 2147483648.

For a positive result, the largest allowed value is only 2147483647.

We store the sign:

sign = -1 if x < 0 else 1

Then we work with the absolute value:

x = abs(x)

The limit depends on the sign:

limit = MAX_NEGATIVE_ABS if sign == -1 else MAX_POSITIVE

Extract the last digit:

digit = x % 10

Remove the last digit:

x //= 10

Before appending the digit, check overflow:

if result > limit // 10:
    return 0

This means multiplying by 10 would already exceed the limit.

The second check handles the boundary case:

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

Then append the digit:

result = result * 10 + digit

Finally, restore the sign:

return sign * result

Testing

def run_tests():
    s = Solution()

    assert s.reverse(123) == 321
    assert s.reverse(-123) == -321
    assert s.reverse(120) == 21
    assert s.reverse(0) == 0

    assert s.reverse(1534236469) == 0
    assert s.reverse(2147483647) == 0
    assert s.reverse(-2147483648) == 0

    assert s.reverse(1463847412) == 2147483641
    assert s.reverse(-8463847412) == 0

    print("all tests passed")

run_tests()