Reverse Integer leetcode — how to handle overflow

问题:

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)

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

回答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

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

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

回答5:

My soluton for this problem is to convert integer inputed to c-string, then everthing will be easy.

class Solution {
public:
  int reverse(int x) {
    char str[11];
    bool isNegative = false;
    int i;
    int ret = 0;

    if ( x < 0 ) {
        isNegative = true;
        x = -x;
    }

    i = 0;
    while ( x != 0 ) {
        str[i++] = x % 10 + '0';
        x = x / 10;
    }
    str[i] = '\0';

    if ( (isNegative && strlen(str) == 10 && strcmp(str, "2147483648") > 0) || (!isNegative && strlen(str) == 10 && strcmp(str, "2147483647") > 0) ) {
        cout << "Out of range!" << endl;
        throw new exception();
    }

    i = 0;
    int strLen = (int)strlen(str);
    while ( str[i] != '\0' ) {
        ret += ((str[i] - '0') * pow(10.0, strLen - 1 - i));
        i++;
    }

    return (isNegative ? -ret : ret);
}

};

回答6:

This works:

public class Solution {
    public int reverse(int x) {
        long tmp = Math.abs((long)x);
        long res = 0;

        while(tmp >= 10){
            res += tmp%10;
            res*=10;
            tmp=tmp/10;          
        }  

        res+=tmp;

        if(x<0){
            res = -res;
        }

        return (res>Integer.MAX_VALUE||res<Integer.MIN_VALUE)? 0: (int)res; 
    }
}

I tried to improve the performance a bit but all I could come up with was this:

public class Solution {
    public int reverse(int x) {

        long tmp = x;
        long res = 0;

        if(x>0){
            while(tmp >= 10){
                res += tmp%10;
                res*=10;
                tmp=tmp/10;          
            }  
        }
        else{
            while(tmp <= -10){
                res += tmp%10;
                res*=10;
                tmp=tmp/10;          
            }  
        }

        res+=tmp;

        return (res>Integer.MAX_VALUE||res<Integer.MIN_VALUE)? 0: (int)res; 
    }
}

Its C# equivalent runs 5% faster than the 1st version on my machine, but their server says it is slower, which can't be - I got rid of extra function call here, otherwise it is essentially the same. It places me between 60-30% depending on the language (C# or Java). Maybe their benchmarking code is not very good - if you submit several times - resulting times vary a lot.

回答7:

---

Solution In Swift 4.0 (in reference to problem from https://leetcode.com/problems/reverse-integer/description/)

func reverse(_ x : Int) -> Int {

    var stringConversion = String(x)
    var negativeCharacter = false
    var finalreversedString = String()
    let signedInt = 2147483647 //Max for Int 32
    let unSignedInt = -2147483647 // Min for Int 32

    if stringConversion.contains("-"){
        stringConversion.removeFirst()
        negativeCharacter = true
    }

    var reversedString = String(stringConversion.reversed())
    if reversedString.first == "0" {
        reversedString.removeFirst()
    }
    if negativeCharacter {
        finalreversedString = "-\(reversedString)"
    } else {
        finalreversedString = reversedString
    }

    return  (x == 0 || Int(finalreversedString)! > signedInt || Int(finalreversedString)! < unSignedInt) ?  0 :  Int(finalreversedString)!

}

回答8:

public static int reverse(int x) {
  boolean pos = x >= +0;
  int y = (pos) ? x : -x;
  StringBuilder sb = new StringBuilder(
      String.valueOf(y));
  sb.reverse();
  int z = Integer.parseInt(sb.toString());
  return pos ? z : -z;
}

public static void main(String[] args) {
  for (int i = -10; i < 11; i++) {
    System.out.printf("%d r= '%d'\n", i, reverse(i));
  }
}

Outputs

-10 r= '-1'
-9 r= '-9'
-8 r= '-8'
-7 r= '-7'
-6 r= '-6'
-5 r= '-5'
-4 r= '-4'
-3 r= '-3'
-2 r= '-2'
-1 r= '-1'
0 r= '0'
1 r= '1'
2 r= '2'
3 r= '3'
4 r= '4'
5 r= '5'
6 r= '6'
7 r= '7'
8 r= '8'
9 r= '9'
10 r= '1'

Did you notice the reverse of 10 and -10? Or 20? You could just return a String, for example

public static String reverse(int x) {
  boolean pos = x >= +0;
  int y = (pos) ? x : -x;
  StringBuilder sb = new StringBuilder(
      String.valueOf(y));
  sb.reverse();
  if (!pos) {
    sb.insert(0, '-');
  }
  return sb.toString();
}

public static void main(String[] args) {
  for (int i = -10; i < 11; i++) {
    System.out.printf("%d r= '%s'\n", i, reverse(i));
  }
}

Works as I would expect.

回答9:

If you are required to return a 32 bit int, and still need to know if there was an overflow perhaps you could use a flag as an extra parameter. If you were using c or c++ you could use pointers to set the flag, or in Java you can use an array (since Java objects pass by value).

Java example:

public class Solution {

     public static int reverse(int x, Boolean[] overflowed) {
            int ret = 0;
            boolean zero = false;
            boolean inputIsNegative = x < 0;
            while (!zero) {
                ret = ret * 10 + (x % 10);
                x /= 10;
                if(x == 0){
                    zero = true;
                }
            }
            //Set the flag
            if ( (inputIsNegative && (ret > 0)) || ((!inputIsNegative) && (ret < 0)))
                overflowed[0] = new Boolean(true);
            else
                overflowed[0] = new Boolean(false);
            return ret;
        }

    public static void main(String[] args) {
        int s = 1000000004;
        Boolean[]  flag = {null};
        System.out.println(s);
        int n = reverse(s,flag); //reverse() will set the flag.
        System.out.println(flag[0].booleanValue() ? "Error: Overflow": n );

    }
}

Notice if the reversed number is too large for a 32 bit integer the flag will be set. Hope this helps.

回答10:

Use string to store the reverse and then print or use long or BigInt

回答11:

public class Solution {
    /**
     * OVERFLOW
     * @param x
     * @return
     */
    public int reverse(int x) {
        int sign = x>0? 1: -1;
        x *= sign;
        int ret = 0;
        while(x>0) {
            ret *= 10;
            if(ret<0 || x>10&&ret*10/10!=ret) // overflow
                return 0;

            ret += x%10;
            x /= 10;
        }
        return ret*sign;
    }

    public static void main(String[] args) {
        assert new Solution().reverse(-2147483412)==-2147483412;
    }
}

回答12:

public class Solution {
    public int Reverse(int x) {

            var sign = x < 0 ? -1 : 1;

            var reverse = 0;

            if (x == int.MinValue)
            {
                return 0;
            }
            x = Math.Abs(x);

            while(x > 0)
            {
                var remainder = x % 10;

                if (reverse > ((int.MaxValue - remainder)/10))
                {
                    return 0;
                }

                reverse = (reverse*10) + remainder;

                x = x/10;
            }

            return sign * Convert.ToInt32(reverse);

    }
}

回答13:

Here we will use long to handle the the over flow:

public class Solution {
 public int reverse(int A) {
    // use long to monitor Overflow
    long result = 0;
    while (A != 0) {
        result = result * 10 + (A % 10);
        A = A / 10;
    }
    if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
        return 0;
    } else {
        return (int) result;
    }
 }
}

回答14:

Well This Suitable Code in Java Can be:-

public class Solution {
    public int reverse(int x) {

        int r;
        long s = 0;

        while(x != 0)
       {
            r = x % 10;

            s = (s * 10) + r;

            x = x/10;
        }
        if(s >= Integer.MAX_VALUE || s <= Integer.MIN_VALUE) return 0;
        else
            return (int)s;  
    }
}

回答15:

My solution without using long:

public class ReverseInteger {

    public static void main(String[] args) {
        int input = Integer.MAX_VALUE;
        int output = reverse(input);
        System.out.println(output);
    }

    public static int reverse(int x) {
        int remainder = 0;
        int result = 0;

        if (x < 10 && x > -10) {
            return x;
        }

        while (x != 0) {
            remainder = x % 10;

            int absResult = Math.abs(result);
            int maxResultMultipliedBy10 = Integer.MAX_VALUE / 10;
            if (absResult > maxResultMultipliedBy10) {
                return 0;
            }

            int resultMultipliedBy10 = absResult * 10;

            int maxRemainder = Integer.MAX_VALUE - resultMultipliedBy10;
            if (remainder > maxRemainder) {
                return 0;
            }

            result = result * 10 + remainder;
            x = x / 10;
        }

        return result;
    }

}

回答16:

here is the JavaScript solution.

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    var stop = false;
    var res = 0;
    while(!stop){
        res = res *10 + (x % 10);
        x = parseInt(x/10);
        if(x==0){
            stop = true;
        }
    }
    return (res <= 0x7fffffff && res >= -0x80000000) ? res : 0
};

回答17:

Taking care if the input is negative

public int reverse(int x) 
{

        long result = 0;
        int res;
        int num = Math.abs(x);

        while(num!=0)
        {
            int rem = num%10;
            result = result *10 + rem;
            num = num / 10;
        }

    if(result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) 
    {
        return 0;
    } 
    else 
    {
        res = (int)result;
        return x < 0 ? -res : res;
    }

}

回答18:

This solution in Java will work:

class Solution {
    public int reverse(int x) {
        long rev = 0, remainder = 0;
        long number = x;

        while (number != 0) {
            remainder = number % 10;
            rev = rev * 10 + remainder;
            number = number / 10;
        }
        if (rev >= Integer.MAX_VALUE || rev <= Integer.MIN_VALUE || x >= Integer.MAX_VALUE || x <= Integer.MIN_VALUE)
            return 0;
        else
            return (int) rev;

    }
}

回答19:

Much simpler solution. Ensure that intermittent result does not exceed INT_MAX or get below INT_MIN

int reverse(int x) {

    int y = 0;

    while(x != 0) {

        if ( (long)y*10 + x%10 > INT_MAX || (long)y*10 + x%10 < INT_MIN) {

            std::cout << "overflow occurred" << '\n'
            return 0;
        }

        y = y*10 + x%10;
        x = x/10;   
    }

    return y;
}

回答20:

Note that there are previous solutions that do not work for input: 1000000045 try this:

public int reverse(int A) {
    int reverse=0;
    int num=A;
    boolean flag=false;
    if(A<0)
    {
    num=(-1)*A;
    flag=true;
    }

    int prevnum=0;
    while(num>0)
    {
        int currDigit=num%10;
        reverse=reverse*10+currDigit;

    if((reverse-currDigit)/10!=prevnum)
            return 0;
        num=num/10;  
        prevnum=reverse;
    }

    if(flag==true)
   reverse= reverse*-1;
return reverse;
}