[LeetCode 7] Reverse Integer

Question

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

Stats

Frequency	3
Diffficulty	2
Adjusted Difficulty	2
Time to use	----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

There’re 2 points that are tricky.

First, overflow issue. Look at the following overflow case for Java int:

+300,000,000 * 10 returns -1294967296
+600,000,000 * 10 returns +1705032704
-300,000,000 * 10 returns +1294967296
-600,000,000 * 10 returns -1705032704
note that max integer is 2,147,483,647

We can observe that if overflow happens, the result is definitely wrong. The result can be either positive or negative.

So, from just +/- sign of the result, we can’t identify an overflow (then how to solve this problem??).

Another interesting thing to note: we actually do not need to handle negative sign. The sign can be preserved during the conversion. Read this post for more.

Without considering overflow, the following code can (almost) work fine:

public int reverse2(int x) {
    int reverse = 0;
    while (x != 0) {
        reverse = reverse * 10 + x % 10;
        x /= 10;
    }
    return reverse;
}

Solution

Two solutions: 1. use long data type. 2. check if ret > 214748364 or ret < –214748364 before multiplying by 10.

My code

First, using long type to avoid overflow.

public class Solution {
    public int reverse(int x) {
        int sign = 1;
        long abs = x;
        long rev = 0;
        if (x < 0) {
            sign = -1;
            abs = 0 - abs;
        }
        // now remove numbers from abs one by one
        // and put these numbers into rev
        while (abs != 0) {
            rev *= 10;
            rev += abs % 10;
            abs /= 10;
        }
        if (rev > Integer.MAX_VALUE) {
            return 0;
        } else {
            return sign * (int) rev;
        }
    }
}

Second, do boundary check in every step. Suggested by Leetcode official book.

Note that max integer is 2,147,483,647

public class Solution {

    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;
    }
}

Woodstock Blog

a tech blog for general algorithmic interview questions