Why does the following program gives wrong answer when I remove "+ mod" from statement check . Problem link: https://www.codechef.com/problems/FFC219B

Question

The statement check is where I don't understand why it shows wrong answer on submission when I write "sum = (solution[R]-solution[L-1])%mod;" instead. Here I have not added mod within the bracket. I don't see how the answer changes by adding a value of taking the mod of same. Problem code in codechef: https://www.codechef.com/problems/FFC219B

#include<iostream>
#define ll long long
#define mod 1000000007   //the modulus we need to take for the final answer
#define endl "\n"
using namespace std;

long long solution[100007] = {0}; //Initialising all the values with zero

int main(){

ios_base :: sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

solution[0] = 0;

ll a1=1,a2=2,a3=3,a4=4;    //The variable initialising as per the problem

 for(int i = 1;i <= 100007;i++){

     ll k=(a1 * a2) % mod * a3 % mod * a4 % mod;

        solution[i] = (solution[i-1]+k)%mod;  //Adding the previous values as we are to find the sum in range

        a1++;

        a2++;

        a3++;

        a4++;
     }

    int t; //Taking input for number of test cases

    cin>>t;

    while(t-->0)
    {

        int L,R;

        cin>>L>>R; //Taking the range input

        long long sum = 0;

        sum = (solution[R]-solution[L-1] + mod)%mod; //statement check & final answer

        cout<<sum<<endl;

       }
    return 0;
}

Already used my vote, so unfortunately cannot now close as a duplicate of [Why does C++ output negative numbers when using modulo?](https://stackoverflow.com/questions/11630321/why-does-c-output-negative-numbers-when-using-modulo) — paddy, Oct 03 '19 at 04:37

score 0 · Accepted Answer · answered Oct 03 '19 at 04:37

The program can give the incorrect answer since the correct answer must always be a positive - not a negative - number.

When you subtract consecutive modulo values, the result may well be negative even though the numbers themselves are increasing (eg, (4^3)%10 - (4^2)%10 = 64%10 - 16%10 = 4-6 = -2), . This means “solution[R]-solution[L-1]” may also well be negative, which means “(solution[R]-solution[L-1]) % mod” will also be negative - although clearly the answer (the number of people affected) must always be positive.

So adding the mod value in this fashion ensures that the result will always be positive.

Why does the following program gives wrong answer when I remove "+ mod" from statement check . Problem link: https://www.codechef.com/problems/FFC219B

1 Answers1