# LeetCode 7: Reverse Integer

## Problem Restatement

We are given a signed 32-bit integer `x`.

We need to reverse its digits.

Examples:

```text
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:

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

which means:

```text
[-2147483648, 2147483647]
```

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | A signed 32-bit integer `x` |
| Output | The integer with its digits reversed |
| Overflow rule | Return `0` if the reversed value leaves the 32-bit signed range |
| Constraint | `-2^31 <= x <= 2^31 - 1` |

Example function shape:

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

## Examples

Example 1:

```text
x = 123
```

Reverse the digits:

```text
321
```

Output:

```text
321
```

Example 2:

```text
x = -123
```

Reverse the digits and keep the negative sign:

```text
-321
```

Output:

```text
-321
```

Example 3:

```text
x = 120
```

Reverse the digits:

```text
021
```

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

```text
21
```

Output:

```text
21
```

Example 4:

```text
x = 1534236469
```

The reversed value would be:

```text
9646324351
```

This is larger than `2147483647`, so the answer is:

```text
0
```

## First Thought: Convert to String

A simple Python solution is:

```python
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:

```text
x = 123
result = 0
```

Take last digit:

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

Take next digit:

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

Take next digit:

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

Now return:

```text
321
```

The only difficult part is overflow.

Before doing:

```text
result = result * 10 + digit
```

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

## Overflow Check

The maximum allowed value is:

```python
MAX_INT = 2**31 - 1
```

The minimum allowed value is:

```python
MIN_INT = -2**31
```

Before appending a digit, we check:

```text
result > MAX_INT // 10
```

If this is true, multiplying by `10` will overflow.

If:

```text
result == MAX_INT // 10
```

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

```text
MAX_INT = 2147483647
```

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

```text
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:

```text
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:

```text
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(log10(|x|))` | We process one decimal digit per loop |
| Space | `O(1)` | Only a few integer variables are stored |

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

```python
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:

```python
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:

```python
sign = -1 if x < 0 else 1
```

Then we work with the absolute value:

```python
x = abs(x)
```

The limit depends on the sign:

```python
limit = MAX_NEGATIVE_ABS if sign == -1 else MAX_POSITIVE
```

Extract the last digit:

```python
digit = x % 10
```

Remove the last digit:

```python
x //= 10
```

Before appending the digit, check overflow:

```python
if result > limit // 10:
    return 0
```

This means multiplying by `10` would already exceed the limit.

The second check handles the boundary case:

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

Then append the digit:

```python
result = result * 10 + digit
```

Finally, restore the sign:

```python
return sign * result
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `123` | Basic positive number |
| `-123` | Negative number |
| `120` | Trailing zero disappears |
| `0` | Zero input |
| `1534236469` | Positive overflow after reversal |
| `2147483647` | Max input overflows when reversed |
| `-2147483648` | Min input overflows when reversed |
| `1463847412` | Reversal stays inside positive bound |
| `-8463847412` | Defensive overflow test outside LeetCode input range |