CODEWITHSUNDEEP
c++integer-overflow
Dumble009
Dumble009

Reputation: 43

c++: int overflows when it is smaller than INT_MAX

I wrote a code like below.

#include <iostream>
#include <string>
#include <stack>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;

long long int N, K;



int main() {
    cin >> N >> K;

    long long int result = 0;
    int IntResult = 0;

    for (long long int i = K; i <= N + 1; i++) {
        result += 1 + (N + 1 - i) * i;
        IntResult += 1 + (N + 1 - i) * i;
    }

    cout << result % (1000000000 + 7) << endl;
    cout << IntResult % (1000000000 + 7) << endl;
    return 0;
}

And when I input "141421 35623", this code outputs below.

141421 35623
220280457
619089693

The correct answer is "220280457". The result of int is wrong.

I put cout in a for loop and checked IntResult's value.

Then I found that IntResult became negative value in a for loop. It's overflowed!

But why? The max value of int is "2147483648". It's greater than "220280457".

And the process in for loop is just an addition, so I can't understand why it is overflowed.

Please help me!

Upvotes: 1

Views: 333

Answers (2)

Adrian Mole
Adrian Mole

Reputation: 51825

In your loop, the expression 1 + (N + 1 - i) * i (which is evaluated as a long long int) quickly and frequently becomes greater than INT_MAX, and this causes integer overflow when you try to add it to the (int) result.

Adding a quick 'check' to your code, as shown below, will demonstrate this:

int main()
{
    cin >> N >> K;
    long long int result = 0;
    int IntResult = 0;
    int count = 0;
    for (long long int i = K; i <= N + 1; i++) {
        // Check for intermediate overflow potential...
        long long int lli = 1LL + (N + 1LL - i) * i;
        if (lli > INT_MAX) cout << lli << " (" << ++count << ")"  << endl;
        result += 1 + (N + 1 - i) * i;
        IntResult += 1 + (N + 1 - i) * i;
    }
    cout << result % (1000000000 + 7) << endl;
    cout << IntResult % (1000000000 + 7) << endl;
    return 0;
}

When I run this code on my platform (32-bit int and 64-bit long long int) with your given inputs (141421 and 35623), the "overflow check" line actually happens 88,498 times! Here are the last three lines of output:

...
2147524241 (88498)
220280457
619089693

Furthermore, even though the above-checked addend may not, in itself, overflow an int, the result of adding it to the existing (potentially non-zero) value in result could still do so. Indeed, changing the 'check' line to this:

if ((lli + result) > INT_MAX) cout << lli << " (" << ++count << ")"  << endl;

shows that the loop overflows on every iteration!

Upvotes: 1

Tony Tannous
Tony Tannous

Reputation: 14876

You overflow on first iteration.

1 + (N + 1 - i) * i

Is smaller than

(N - i)*i

First iteration:

(141421-35623)*35623

Whoops already overflow, which is UB in signed integers.

IntResult % (1000000000 + 7)

Happens afterwards, and has no meaning as IntResult contains a unknown value.

Upvotes: 1

Related Questions