CODEWITHSUNDEEP
c++integeroverflow
Thanos
Thanos

Reputation: 386

Problem with Reversing Large Integers On Leetcode?

I was working on this problem from Leetcode where it has this requirement of reversing numbers whilst staying within the +/-2^31 range. I checked out other solutions made for this problem, and from there created my own solution to it. It worked successfully for numbers ranging from 10 to less than 99,999,999. Going more than that(when trying to submit the code to move to the next question) would throw an error saying:

"Line 17: Char 23: runtime error: signed integer overflow: 445600005 * 10 cannot be represented in type 'int' (solution.cpp)"

This was the input given when trying to submit the code: 1534236469

My code

class Solution {
public:
    int reverse(int x) {
      int flag = 0;
      int rev = 0;
      if (x >= pow(2, 31)) {
          return 0;
      } else {
        if (x < 0) {
            flag = 1;
            x = abs(x);
        }
        while(x > 0) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        if (flag == 1) {
            rev = rev*(-1);
        }
        
    return rev;    
    }  
    }
};

As you can see from my code, I added an if statement that would basically return 0 if the number was greater than 2^31. Unfortunately, this was wrong.

Can anyone explain how this can be fixed? Thank you in advance.

Upvotes: 0

Views: 1065

Answers (2)

Tejas Patil
Tejas Patil

Reputation: 9

 public static int reverse(int x) {
        boolean isNegative = false;
        if (x < 0) {
            isNegative = true;
            x = -x;
        }
        long reverse = 0;
        while (x > 0) {
            reverse = reverse * 10 + x % 10;
            x=x/10;
        }
        if (reverse > Integer.MAX_VALUE) {
            return 0;
        }
        return (int) (isNegative ? -reverse : reverse);
    }

Upvotes: 1

red_demise
red_demise

Reputation: 36

Problem statement asks to return 0 if reversed number does not belong to integer range :

If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

In your code you checked if input fits in integer range but their arises a corner case when the integer has 10 digits and last digit is >2 (and for some cases 2).

Lets consider the input 1534236469: 1534236469 < 2^31 - 1

so program executes as expected now lets trace last few steps of program execution : rev = 964632435 and x = 1 problem arises when following statement is executed :

rev = rev * 10 + x % 10;

Now, even though input can be represented as integer rev * 10 i.e. 9646324350 is greater than integer range and correct value that should be returned is zero

Fix ?

1. Lets consider 10 digit case independently

Even though this can be done, it gives rise to unnecessary complications when last digit is 2

2. Make rev a long integer

This works perfectly and is also accepted, but sadly this is not expected when solving this problem as statement explicitly asks to not use 64-bit integers

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

3. Checking before multyplying by 10 ?

This works as expected. Before multyplying rev by 10 check if it is >= (pow(2,31)/10)

while(x > 0) {
            if (rev >= pow(2, 31)/10 )
                return 0;
            rev = rev * 10 + x % 10;  
            x /= 10;
        }

I hope this solves your doubt !! Comment if you find something wrong as this is my first answer.

Note : The following if statement is unnecessary as input is always a 32-bit integer

Given a signed 32-bit integer x

if (x >= pow(2, 31)) {
          return 0;
      }

Edit : As most of the comments pointed it out, instead of pow(2,31), use INT_MAX macro as it suffices here.

Upvotes: 2

Related Questions