CODEWITHSUNDEEP
c++overflow
duduShh
duduShh

Reputation: 11

Reverse an integer in leetcode

I was trying to solve the reverse integer problem, where we have to keep in mind to deal with overflow.

Reading others solutions and tried out, I wrote my solution

class Solution {
public:
  int reverse(int x) {
  int result = 0;
  int old_result = 0;
  while(x) {
    old_result = result;
    result = result*10 + x%10;
    if ((result-old_result*10)!=x%10)
        return 0;
    x = x/10;
  }
  return result;
  }
};

And the answer was not accepted because overflow was not handled well. It turned out changing

if ((result-old_result*10)!=x%10)

to

if ((result-x%10)/10!=old_result)

would make things work.

I feel these lines are doing the same check. Not sure why one passes and one fails.

Can anyone help explain?

Upvotes: 1

Views: 362

Answers (3)

Jarod42
Jarod42

Reputation: 217255

Note that overflow with signed numbers is implementation specific UB, so I suggest to use unsigned instead. Then considering that it use similar property than unsigned, and assuming that result = result*10 + x%10; overflows. Then:

result -= old_result * 10;

"reverts" the overflow in the same way.

whereas the following is true

(result - x % 10) == old_result * 10; // With possible overflow in both side.

Dividing by 10 on both side removes the overflow only with the simplification

(result - x % 10) / 10 == old_result;
// overflow on left side (before division). No overflow on right side.

Upvotes: 0

chux
chux

Reputation: 153457

   result = result*10 + x%10;

   if ((result-old_result*10)!=x%10)
   // or
   if ((result-x%10)/10!=old_result)

Both are bad when coded after result*10 + x%10; as the overflow may already have happened.

int overflow is to be avoided for well behaved code.

Rather than depend on overflow behaving as certain way, detect if result*10 + x%10 will overflow before computing it. 

  // for positive numbers
  int max = std::numeric_limits<int>::max
  while(x) {
    int digit = x%10;
    if (result >= max/10 && (result > max/10 || digit > max%10)) {
      Overflow();
    }
    result = result*10 + digit;
    x = x/10;
  }

Upvotes: 1

Algirdas Preidžius
Algirdas Preidžius

Reputation: 1767

I feel these lines are doing the same check. Not sure why one passes and one fails.

Not necessarily. If the value of old_result ever was more than (or equal to) std::numeric_limits<int>::max () / 10 + 1, the expression old_result*10 would overflow, which would give you the wrong answer.

Overflow of integral types are undefined behavior. This is the quite from C++ (C++11/C++14/C++17) standard draft (I don't have access for the full version of standard, and, in majority of cases, it is good enough):

If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined.

The second form (reordered) of if removes the multiplication - effectively increasing the range of values, that can be used in old_result.

Upvotes: 1

Related Questions