# 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

``````Integer.MAX_VALUE = 2147483647

Integer.MIN_VALUE = -2147483648
``````

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

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

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.

``````//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.

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

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

``````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;
}
``````