LeetCode Reverse Integer: Overflow Detection

Overview

The key to this LeetCode Reverse Integer problem is the overflow detection, the algorithm is simple and you do not have to keep each single digits.

LeetCode Reverse Integer Problem

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Have you thought about this?Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

Overflow Detection and the Solution

A very simple and straightforward problem, just pay attention the notes including the (1) leading zeros and (2) overflow issues. I think the extra parameter in the last sentence here probably refer to some error message (not very sure). For the overflow problem, I have another post to discuss the best practices about how to detect over flow in this post: “Detect Integer Overflow“. The following C++ code is accepted by LeetCode OJ to pass this Reverse Integer problem:

int reverse(int x) {
    bool positive = (x >= 0);
    x = abs(x);
    int ret = 0;
    bool overflow = false;
    vector<int> digits;
    while (x) {
        digits.push_back(x % 10);
        x /= 10;
    }
    for (int i = digits.size() - 1, multiplier = 1; i >= 0 && !overflow; --i, multiplier *= 10) {
        if (INT_MAX / multiplier < digits[i] || INT_MAX - ret < digits[i] * multiplier)
            overflow = true;
        ret += digits[i] * multiplier;
    }
    if (overflow) return 0;
    if (!positive) ret = -ret;
    return ret;
}

More comment, if you unlock the solution of this problem from LeetCode OJ, you could see the following Java code

public int reverse(int x) {
   int ret = 0;
   while (x != 0) {
      // handle overflow/underflow
      if (Math.abs(ret) > 214748364) {
         return 0;
      }
      ret = ret * 10 + x % 10;
      x /= 10;
   }
   return ret;
}

The solution there directly detect the return value which in my opinion is incorrect because, (Math.abs(ret) > 214748364) does not imply or does not make sure ret = ret * 10 + x % 10; won’t get overflow!

Summary

Again, the key to this LeetCode Reverse Integer problem is the overflow detection, the algorithm is simple and you do not have to keep each single digits.

Written on April 18, 2013