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

0.1. Examples

• 321 -> 123
• 100 -> 1
• -123 -> -321
• 10⁹+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⁹+7 = 1000000007. The range of integers is from -2³¹ to 2³¹-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⁹+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.