###### tags: `leetcode`
# Leetcode #7 Reverse Integer
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
```typescript=
Input: 123
Output: 321
```
Example 2:
```typescript=
Input: -123
Output: -321
```
Example 3:
```typescript=
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.
## first approach, int(str(x)[::-1])
Reversing on the base on ten.
### fail #0
```python=
class Solution:
def reverse(self, x: int) -> int:
if x >= 0:
return int(str(x)[::-1])
else:
return int(str(x)[-1:0:-1])
```
Wrong Answer
```python=
Input
-123
Output
321
Expected
-321
```
### fail #1
```python=
class Solution:
def reverse(self, x: int) -> int:
if x >= 0:
return int(str(x)[::-1])
else:
return -int(str(x)[-1:0:-1])
```
Wrong Answer
```python=
Input
1534236469
Output
9646324351
Expected
0
```
### fail #2
```python=
class Solution:
def reverse(self, x: int) -> int:
if (x >> 32) != 0: # more than 32 bits
return 0
if x >= 0:
return int(str(x)[::-1])
else:
return -int(str(x)[-1:0:-1])
```
Wrong Answer
```python=
Input
-123
Output
0
Expected
-321
```
#### Issue: How Python3 store integer？
I think, Python3 will fill-up the left-hand-side with 1 (for positive) and 0 (for negative).
But! When using `bin()`, `bin()` represents integers in a weird way. It prints a sign and a binary of an absolute value.
But the bit-shift still works on an correct 2's complement scheme.
Actually, results of bit-shifting on 2's complement and on sign-and-magnitude will be the same.
##### Bound of int in py3
https://stackoverflow.com/questions/7604966/maximum-and-minimum-values-for-ints
- digest #0
The plain int type is unbounded.
However, you might actually be looking for the machine's word size. That's still available in Python 3 as sys.maxsize.
- digest #1
sys.maxsize on york's machine's py3
```python=
import sys
max= sys.maxsize # 9223372036854775807 = 2**63-1
min=-sys.maxsize-1 # -2**63
```
- digest #2
As pointed out by others, Python 3's int does not have a maximum size, but if you just need something that's guaranteed to be higher than any other int value, then you can use the float value for Infinity, which you can get with float("inf").
### fail #3
```python=
class Solution:
def reverse(self, x: int) -> int:
if x > (2**31 -1):
return 0
if x < (-2**31):
return 0
if x >= 0:
return int(str(x)[::-1])
else:
return -int(str(x)[-1:0:-1])
```
Wrong Answer
```python=
Input
1534236469
Output
9646324351
Expected
0
```
I checked the overflow of the input but I didn't check the overflow of the output.
### success
```python=
class Solution:
def reverse(self, x: int) -> int:
if x > (2**31 -1):
return 0
if x < (-2**31):
return 0
if x >= 0:
if int(str(x)[::-1]) <= (2**31 - 1):
return int(str(x)[::-1])
return 0
else:
if -int(str(x)[-1:0:-1]) >= (-2**31):
return -int(str(x)[-1:0:-1])
return 0
```
Details
```typescript=
Runtime: 40 ms, faster than 53.11% of Python3 online submissions for Reverse Integer.
Memory Usage: 13.9 MB, less than 5.45% of Python3 online submissions for Reverse Integer.
```
### solution from others #0
ref =
https://leetcode.com/problems/reverse-integer/discuss/4055/Golfing-in-Python
```python=
class Solution(object):
def reverse(self, x):
s = (x > 0) - (x < 0) # positive-->1; negative-->-1; 0-->0
r = int(str(x*s)[::-1]) # x*s = abs(x)
return s*r * (r < 2**31) # put the sign back and
```
Though it pass the test of the Leetcode website, its edges cases are not handled well.
Read my https://hackmd.io/kXZuqLftSz6bl8Fl_N3X7w as my note
### solution from others #1
#### Not built-in but no need for import
```python=
>>> a=1 # have to give it a name
>>> a.bit_length() # we can't do 1.bit_length()
1
```
Read my https://hackmd.io/XL4q9mdnQDC_VUBGV6GQyA as my test
### solution from others #2
```python=
class Solution:
def reverse(self, x):
sign = [1,-1][x < 0]
rst = sign * int(str(abs(x))[::-1])
return rst if -(2**31)-1 < rst < 2**31 else 0
```
#### feature #0
```python=
sign = [1,-1][x < 0]
```
#### feature #1
```python=
return rst if -(2**31)-1 < rst < 2**31 else 0
```
## second approach, use `mod 10`, pop and push
### success
```python=
class Solution:
def reverse(self, x: int) -> int:
if x > (2**31 -1) or x < (-2**31):
return 0
if x >= 0:
a = 0
while x != 0:
a = a * 10 + x % 10
x = x // 10
if a <= (2**31 - 1):
return a
return 0
else:
b = 0
while x != 0:
b = b * 10 + (x % -10)
x = -(x // -10)
if b >= (-2**31):
return b
return 0
```
#### the usage of `mod` and `%` on minus int
```python=
>>> -1 % 10
9
>>> -11 % 10
9
>>> -19 % 10
1
>>> -1 % -10
-1
```
```python=
>>> 1 / 10
0.1
>>> 1 // 10
0
>>> -11 // 10
-2
>>> -10 // 10
-1
>>> -10 // -10
1
```
### another's solution #0
grammar ref = https://ell.stackexchange.com/questions/105758/anothers-vs-another
ref =
https://leetcode.com/problems/reverse-integer/discuss/4060/My-accepted-15-lines-of-code-for-Java
#### 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) // overflow check!!
{ return 0; }
result = newResult;
x = x / 10;
}
return result;
}
```
#### Smart overflow check!!
```java=
f_x = fun(x) // function of x
frev_f_x = frev(f_x) // reverse function of function of x
if (frev_f_x != x) // overflow check!!
{ return 0; }
```
### another's solution #1
ref=
https://leetcode.com/problems/reverse-integer/discuss/132861/3-lines-Python-Solution
- Convert x to positive
- Pop and push
- Put the sign back
- Check the range
```python=
class Solution:
def reverse(self, x):
sign = [1,-1][x<0]
rev, x = 0, abs(x)
while x:
x, mod = divmod(x, 10)
rev = rev*10 + mod
return sign*rev if -pow(2,31) <= sign*rev <= pow(2,31)-1 else 0
```
### another's solution #2
Using larger int system to play with overflow
Java
```java=
class Solution {
public:
int reverse(int x) {
long long res = 0;
while(x) {
res = res*10 + x%10;
x /= 10;
}
return (res<INT_MIN || res>INT_MAX) ? 0 : res;
}
};
```
## Review
### digit reversion
- str
- convert x to str
- reverse str
- str --> int
- pop and push
- pop:
- last_digit = x // 10
- x = x // 10 ## to update x
- push:
- y = y * 10 + last_digit
### overflow handling
- python3 use big number int so no overflow
- to mimic overflow
- check every time to make sure never overflow
- have to know the condition where overflow is just about to happen
- check at every pop-and-push cycle
- check whether $f^{-1}(f(x)) = x$
- use larger system to catch
- then check whether it is out of bound
- ref = https://leetcode.com/problems/reverse-integer/discuss/4057/Shortest-code-possible-in-c%2B%2B
Sign in with Wallet
Connect another wallet