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

Avatar for Tanishq Chaudhary

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

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.