CODEWITHSUNDEEP
java
Zhinkk
Zhinkk

Reputation: 347

Why does reversing an operation allow overflow handling?

A leetcode problem (https://leetcode.com/problems/reverse-integer/description/) asks to reverse an integer, which is simple enough, but wants the user to return 0 if there is any overflow. Doing this with long is also simple, as you can check if it's greater than INTEGER.MAX_INT or MIN_INT in java. But if only 32 bit ints are allowed, how can this be accomplished?

The following solution is shown:

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

    while (x != 0)
    {
        int tail = x % 10;
        int newResult = result * 10 + tail;
        if ((newResult - tail) / 10 != result)
        { return 0; }
        result = newResult;
        x = x / 10;
    }

    return result;
}

I'm confused why this works. Why does "reversing" the operation, and comparing it to the previous result successfuly check for overflow?

If you started with x, then said: x2 = (x*10) + b, wouldn't (x2-b)/10 always equal x? Since a positive overflow always loops around to the min value, and a negative overflow always loops around to the max value. How does this check for overflow? I would love any clarifications on this.

Upvotes: 0

Views: 58

Answers (1)

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272487

If you started with x, then said: x2 = (x*10) + b, wouldn't (x2-b)/10 always equal x?

No. Your intuition about "looping" is correct for addition and subtraction - it's like moving back and forth on a clock face around 12 o'clock.

However, this doesn't apply to multiplication, as this example demonstrates:

int x = 2_000_000_000;
int y = x * 10;
int z = y / 10;

System.out.println(x);   // 2000000000
System.out.println(z);   // -147483648

Live demo.

So to answer the top-level question:

Why does "reversing" the operation, and comparing it to the previous result successfully check for overflow?

Because when overflow occurs, "reversing" this sequence of operations won't get you back to the input value.

Upvotes: 1

Related Questions