Reverse an integer in leetcode

Question

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?

Algirdas Preidžius · Answer 1 · 2017-01-16T23:48:40.077

1

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.

edited Jan 16 '17 at 23:48

answered Jan 16 '17 at 22:59

Algirdas Preidžius

1,769
3
14
17

@chux My bad. I thought wrong (was trying to find definitive answer for this in C++ standard (for C++11, C++14, and C++17), and, apparently, I am not used to reading it, yet). Will update my answer. – Algirdas Preidžius Jan 16 '17 at 23:43
@chux What I meant is, that I was trying to find the definitive answer, _after_ you pointed this out to me (and was searching for the relevant quote for all this time). – Algirdas Preidžius Jan 16 '17 at 23:50
"The second form (reordered) of if removes the multiplication", but too late. The prior `result*10` may overflow, rendering subsequent code of no certain value. – chux - Reinstate Monica Jan 16 '17 at 23:50
@chux Yes, you are correct. Due to the fact that OP mentioned that _second form_ started working correctly, I didn't pay enough attention to the actual code, but, rather, looked at the differences between those statements. So, due to those mistakes, I guess that it's time to rest for me :/ – Algirdas Preidžius Jan 17 '17 at 00:04
Thanks for the spec lookup – chux - Reinstate Monica Jan 17 '17 at 00:05

chux - Reinstate Monica · Answer 2 · 2017-01-16T23:56:17.610

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

Jarod42 · Answer 3 · 2017-01-17T00:05:43.370

0

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.

edited Jan 17 '17 at 00:05

answered Jan 16 '17 at 22:53

Jarod42

203,559
14
181
302

[This answer](http://stackoverflow.com/a/33186429/2410359) indicates overflow with signed numbers is undefined. So is it "implementation specific" or undefined? – chux - Reinstate Monica Jan 16 '17 at 23:25

Reverse an integer in leetcode

3 Answers3