0

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.

Thanos
  • 386
  • 2
  • 13
  • Reversing integers is very easy if you hold them as a string (decimal). – Richard Critten Feb 26 '21 at 12:55
  • 2
    Any use of `pow` with integer values only, especially to raise 2 to an integer power, is automatically wrong. This is not what `pow` is for, and this kind of a problem is just an excersize in basic math. Unfortunately sites like "Leetcode" are not C++ tutorial sites and offer little value in teaching anyone the fundamentals of C++. That's not what these sites are for. They're just a list of random coding puzzles, and to really learn how to do these things in C++, [a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) is needed. – Sam Varshavchik Feb 26 '21 at 13:08
  • Reversing 1534236469 gets you outside that range. You should check your result, not the input. (And the limit is the integer `1 << 31`, not the floating-point number `pow(2,31)`.) – molbdnilo Feb 26 '21 at 13:19
  • I don't get it I've learned everywhere that using pow raises the power of the number to what you want?? – Thanos Feb 26 '21 at 13:32
  • 1
    @Thanos because they all convert to floating-point https://en.cppreference.com/w/cpp/numeric/math/pow And now you are in that wonderful place were you have to workout if a particular floating point representation can hold the integer value exactly. Best to avoid even asking that question. – Richard Critten Feb 26 '21 at 13:34
  • @Thanos *I've learned everywhere that using pow raises the power of the number to what you want* -- [Well, this will surprise you](https://stackoverflow.com/questions/25678481/why-does-pown-2-return-24-when-n-5-with-my-compiler-and-os). Binary floating point is not schoolbook, base 10 arithmetic. The bottom line is to not use floating point arithmetic or functions for integer-based problems. That's another thing "Leetcode" and other such sites seem to leave out. – PaulMcKenzie Feb 26 '21 at 13:50

2 Answers2

2

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.

red_demise
  • 36
  • 3
  • 1
    Thank you for the response it really helped me understand this in a better. However, with the whole INT_MAX thing, how would you use it instead of the pow? – Thanos Feb 26 '21 at 14:45
  • [Numeric Limits](https://en.cppreference.com/w/c/types/limits) page describes use of these limits. You can refer this or instead a quick google search will lead to more readable posts. – red_demise Feb 26 '21 at 15:56
  • Alright will do, thank you very much for the help – Thanos Feb 27 '21 at 14:10
1
 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);
    }
Dharman
  • 30,962
  • 25
  • 85
  • 135
Tejas Patil
  • 11
  • 1