integer overflow in below program for max int 1000 000(which is under range of int)

Question

I was solving a problem on spoj,SPOJ CARDS The problem is easy and i am getting correct output for small numbers,But it seems to spoj is not accepting due to integer overflow , Then what integer type should i use?

OR is there any other problem that they are not accepting it ?I also don't know the test cases in which it might be failing

some of the accepted solution of other guys that seem to use the same logic and there solution is accepted accepted sol

Test case:

      2
      3
      7

output:

      15
      77

.

    #include<bits/stdc++.h>
    using namespace std;
    int main(){
        int t;
        cin>>t;
        while(t--){
            int n;
            cin>>n;
            unsigned long long int sum1=0;
            unsigned long long int sum2=0;
            sum1=((n*(n-1))/2)%1000007;
          //  cout<<"sum1 is"<<sum1;
            sum2=(n*n+n)%1000007;
            cout<<(sum1+sum2)%1000007<<endl;

        }

    }

EDIT

The answer get accepted when i use unsigned long long n but max value of n was 1000 000 then it should also get accepted in int n because nmax is under range of int

"#include<bits/stdc++.h>" - Don't do that. That header is for the implementation to use, not you. — Jesper Juhl
– Jesper Juhl, Commented Jan 9, 2019 at 19:16
At what size input does it start to fail? Seems like (n*n+n) would be the best candidate for an overflow. — François Andrieux
– François Andrieux, Commented Jan 9, 2019 at 19:27
A good hint is provided in the link you gave: first divide by 2 ... — Damien
– Damien, Commented Jan 9, 2019 at 19:31
This sum1=((n*(n-1))/2)%1000007 looks dangerous when using unsigned types, if the value for n that is entered can be less than, or equal to, zero. — Jesper Juhl
– Jesper Juhl, Commented Jan 9, 2019 at 19:31

Sid S · Accepted Answer · 2019-01-09 21:10:37Z

2

Your code overflows the range of int in the n * (n - 1) and n * n multiplications when n is large.

It has to do with the order of operations. For instance, (n * n + n) % 1000007; Here, first n * n is calculated. The result is bigger than you can fit in an int, so you get integer overflow. The resulting int value is smaller than it should be because of the overflow. To that too small value, n is added. This results in another int that is too small. That too small value is divided by 2. Finally, the % is carried out.

A simple workaround is to declare n like this:

unsigned long long n;

By changing the type of n to unsigned long long, each step in the calculation will be of type unsigned long long since the first step of the calculation is carried out on n.

edited Jan 9, 2019 at 21:10

answered Jan 9, 2019 at 19:51

Sid S

6,1152 gold badges20 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user10891599 Over a year ago

sorry the solution is accepted but why this happened range was 1 000 000 only? which is under int range

Sid S Over a year ago

@user10891599, It happens because there are interim results that exceed the range of int.

Collectives™ on Stack Overflow

integer overflow in below program for max int 1000 000(which is under range of int)

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related