# 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.

**Contents**hide

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

### 0.1. Examples

- 321 -> 123
- 100 -> 1
- -123 -> -321
- 10
^{9}+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 10^{9}+7 = 1000000007. The range of integers is from -2^{31} to 2^{31}-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 10^{9}+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.

### Recommended Posts

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

June 13, 2022

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

June 13, 2022

Please write the proof.

This solution need an amendment for 2 digit number.