# Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

**Example 1:**

```
Input:
 123

Output:
 321
```

**Example 2:**

```
Input:
 -123

Output:
 -321
```

**Example 3:**

```
Input:
 120

Output:
 21
```

**Note:**\
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: \[−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

## Solution & Analysis

```java
Integer.MAX_VALUE = 2147483647

Integer.MIN_VALUE = -2147483648
```

### LeetCode - Approach Pop and Push Digits & Check before Overflow

<https://leetcode.com/problems/reverse-integer/solution/>

简而言之就是pop push每个digit，并且在这么做之前检查是否overflow。

We can build up the reverse integer one digit at a time.

Reversing an integer can be done similarly to reversing a string. We want to repeatedly "pop" the last digit off of `x` and "push" it to the back of the `rev`. In the end, `rev` will be the reverse of the `x`.

To "pop" and "push" digits without the help of some auxiliary stack/array, we can use math.

```java
//pop operation:
pop = x % 10;
x /= 10;

//push operation:
temp = rev * 10 + pop;
rev = temp;
```

However, this approach is dangerous, because the statement `temp = rev⋅10 + pop` can cause overflow.

Luckily, it is easy to check beforehand whether or this statement would cause an overflow.

* If `temp =  rev⋅10 + pop` causes overflow, then it must be that `rev >= Integer.MAX_VALUE / 10`;
* If `rev > Integer.MAX_VALUE / 10`, then temp = rev \* 10 + pop is guaranteed to overflow
* If `rev == Integer.MAX_VALUE / 10`, then `temp = rev * 10 + pop` will overflow if and only if `pop > 7`

Similar logic can be applied when `rev` is negative.

```java
class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}
```

**Complexity Analysis**

* Time Complexity: O(log(x)). There are roughly log 10 ​ (x) digits in x.
* Space Complexity: O(1)

### 最简短的方法 - 用Long类型

<https://leetcode.com/problems/reverse-integer/discuss/4060/My-accepted-15-lines-of-code-for-Java/165595>

```java
class Solution {
    public int reverse(int x) {
        long res = 0;
        while (x != 0) {
            res *= 10;
            res += x % 10;
            x /= 10;
        }

        return (int) res == res ? (int) res : 0;
    }
}
```

### 不使用Long类型

<https://leetcode.com/problems/reverse-integer/discuss/4060/My-accepted-15-lines-of-code-for-Java>

```java
public int reverse(int x)
{
    int result = 0;

    while (x != 0)
    {
        int tail = x % 10;
        int newResult = result * 10 + tail;
        if ((newResult - tail) / 10 != result) { return 0; }
        result = newResult;
        x = x / 10;
    }

    return result;
}
```