Reverse Integer leetcode -- how to handle overflow

Question

The problem is: Reverse digits of an integer.

Example1: x = 123, return 321

Example2: x = -123, return -321

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

The solution from the website I search is:

public class Solution {

     public static int reverse(int x) {
            int ret = 0;
            boolean zero = false;
            while (!zero) {
                ret = ret * 10 + (x % 10);
                x /= 10;      
                if(x == 0){
                    zero = true;
                }
            }
            return ret;   
        }

    public static void main(String[] args) {
        int s = 1000000003;
        System.out.println(reverse(s));
    }

}

However when s = 1000000003, the console prints -1294967295 instead of 3000000001. So this solution still does not solve the overflow problem if we cannot use exception. Any help here?(Although there is a hint: add an extra parameter, I still cannot figure out what parameter I should add)

Solution 1

There's no need for any data type other than int. Just make sure when there's an operation that increases a number, reversing the operation should give you the previous number. Otherwise, there's overflow.

public int reverse(int x) {
    int y = 0;

    while(x != 0) {
        int yy = y*10 + x%10;

        if ((yy - x%10)/10 != y) return 0;
        else y = yy;

        x = x/10;   
    }
    return y;
}

Solution 2

Above most of the answers having a trivial problem is that the int variable possibly might overflow. You can try this : x = -2147483648 as parameter. There has an easy way to solve the problem. Convert x to long, and check if the result >= Integer.MAX_VALUE, otherwise return 0. The solution passed all test cases on https://leetcode.com/problems/reverse-integer/

This is a java version.

public int reverse(int x) {
        long k = x;
        boolean isNegtive = false;        
        if(k < 0){
            k = 0 - k;
            isNegtive = true;
        }

        long result = 0;
        while(k != 0){
            result *= 10;
            result += k % 10;
            k /= 10;
        }

        if(result > Integer.MAX_VALUE) return 0;
        return isNegtive  ? 0 - ((int)result) : (int)result;
    }

C# version

    public int Reverse(int x)
    {
        long value = 0;
        bool negative = x < 0;
        long y = x;
        y = Math.Abs(y);

        while (y > 0)
        {
            value *= 10;
            value += y % 10;
            y /= 10;
        }

        if(value > int.MaxValue)
        {
            return int.MaxValue;
        }

        int ret = (int)value;

        if (negative)
        {
            return 0 - ret;
        }
        else
        {
            return ret;
        }
    }

Python version

def reverse(self, x):                
    isNegative = x < 0
    ret = 0
    x = abs(x)
    while x > 0:
        ret *= 10
        ret += x % 10
        x /= 10
    if ret > 1<<31:
        return 0

    if isNegative:
        return 0 - ret
    else:
        return ret

Solution 3

This java code handles the overflow condition:

public int reverse(int x) {

    long reverse = 0;
    while( x != 0 ) {
       reverse = reverse * 10 + x % 10;
       x = x/10;
    }

    if(reverse > Integer.MAX_VALUE || reverse < Integer.MIN_VALUE) {
        return 0;
    } else {
        return (int) reverse;
    }
}

Solution 4

This is an old question, but anyway let me have a go at it too! I just solved it on leetcode. With this check, you never hit the overflow/ underflow in either direction, and I think the code is more concise than all the listed codes. It passes all test cases.

public int reverse(int x) {
    int y = 0;
    while(x != 0) {
        if(y > Integer.MAX_VALUE/10 || y < Integer.MIN_VALUE/10) return 0;
        y *= 10;
        y += x % 10;
        x /= 10;
    }
    return y;
}

Solution 5

you can try this code using strings in java

class Solution {
    public int reverse(int x) {
        int n = Math.abs(x);
        String num = Integer.toString(n);
        StringBuilder sb = new StringBuilder(num);
        sb.reverse();
        String sb1;
    
        sb1 = sb.toString();
        
        int foo;
        try {
            foo = Integer.parseInt(sb1);
        }
        catch (NumberFormatException e){
            foo = 0;
        }
        if(x < 0){
            foo *= -1;
        }
        
        return foo;
    }
}

View more solutions

Comments

[Olimpiu POP]

I think the question was how to use the method signature and implement it maybe alter it by adding just an extra parameter

[Peter Lee]

so far this is the best solution.

[Corvin]

Well, it might work for Java, but it's not making sense - no integer should be more than Integer.MAX_VALUE - that's the whole point of MAX_VALUE. So, comparison ( result > Integer.MAX_VALUE) is always false.

[gidim]

result is a long, not an int.

[Alex]

This is smart, but I feel like you are treating. What if you were asked to reverse a long? Will you try to store the value into BigInteger in that case?

[Leonid Vasilev]

Current version of the problem states that you can't use long: Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range.

[Crystal]

this didn't return 0 as expected for x=1534236469

[Leomord]

It works. But why Integer.MAX_VALUE and Integer.MIN_VALUE must be divided by 10?

[Xgh05t]

@Leomord well I think the reason I did that was that we will be adding x % 10 to the number so 0-9 is going to be added or substracted which could result in an over/under flow, so it is acting like a buffer to allow those values to be taken into account as well, you could alternatively add another if statement check after multiplication and pre addition and not use the div by 10.

[RATHI]

This is cheating. What about a environment where you have only INT as the max or like very log memory chipsets.

[Techno Cracker]

Java solution does not work when you have input number 1534236469.

[Sihat Afnan]

this generates following runtime error runtime error: signed integer overflow: 964632435 * 10 cannot be represented in type 'int'