# Reverse integer | InterviewBit | LeetCode | Solution Explained

I explain the “expected” solution to Reverse integer, present on both InterviewBit & LeetCode. IB Problem Link. LC Problem Link.

## 0. Reverse integer: Problem Discussion

### 0.0. IO Format

• input:
• a 32 bit signed integer (positive or negative integer)
• output:
• the reversed integer. if it goes out of range, then output 0.
• constraints:
• the system does not have 64 bit storage for integers

• 321 -> 123
• 100 -> 1
• -123 -> -321
• 109+7 -> 0

## 1. Reverse integer: First Thoughts / Brute-force Solution

The solution is extremely simple if we are allowed languages like Python, or if we have 64 bit integer availability.

```int Solution::reverse(int A) {
long long multi = (A < 0) ? -1: +1;
if (A < 0) {
A = -A;
}
long long rev = 0;

while(A) {
rev = rev * 10 + A % 10;
A /= 10;
}
long long ans = rev * multi;
if ((ans > pow(2, 31) - 1) or (ans < - pow(2, 31))) {
ans = 0;
}
return (int) ans;
}```
```class Solution:
def reverse(self, A):
multi = -1 if A < 0 else 1
ans = multi * int(str(A)[int(A < 0):][::-1])
if not (-2**31 <= ans <= 2**31-1): return 0
else: return ans```

## 2. Reverse integer: Observations & Logic

### 2.0. Intuitions

Given that we can’t store 64 bit integer, the next idea is to rely on 32 bit integer alone, to store the reversed value.

Now it really won’t be of any issue, until we get to cases like 109+7 = 1000000007. The range of integers is from -231 to 231-1 = 2 billion something. This means that we are looking at the reversed number 7000000001. Overflow!

### 2.1. Preventing Overflow

How can we prevent overflow? Well what we can focus on is the very last step, right before we overflow. When we have a case like 109+7 = 1000000007, we won’t overflow until the very very last step, where we do 700000000 * 10 + 1. The 700000000 * 10 is the real issue. So, we catch the `rev` at one step before doing * 10. That is, we’ll check if rev > INT_MAX / 10 (note how we shifted the 10!). If that is true, then we are going to overflow (still haven’t, but going to), so we return early.

Similar is the case for INT_MIN.

## 3. Reverse integer: Optimized Implementation

### 3.0. Code

```int Solution::reverse(int A) {
int rev = 0;
while (A) {
if(rev > INT_MAX / 10 || rev < INT_MIN / 10) return 0;
rev = rev * 10 + A % 10;
A /= 10;
}
return rev;
}
```

### 3.1. Complexity Analysis

• Time: `O(logN)`, where N is the number of digits – 10 in our case.
• Space: `O(1)`, since we only ever store some integers.

##### Tanishq Chaudhary Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Assign Mice to Holes | InterviewBit | Solution Explained

June 13, 2022

1. Srishti Chopra :July 23, 2022 at 11:29 am

2. Makarand :August 16, 2022 at 11:06 am
3. Gopal :November 14, 2022 at 5:53 pm