Confusion regarding modulo operaor

Referring to this solution (got AC) for the question, i came across teh confusion regarding modulo operator.
I initially framed the array fib[] this way


and this gave WA. I, just in case,changed the above to

for(i=2;i<=MAX;i++) {
fib[i]=(fib[i-1]+fib[i-2])%mod; }

and this gave AC. As far as i know (a+b)%mod = a%mod + b%mod, then why such??

Not so.

Let a = 4 , b = 4 , p = 7 .

(a+b) mod p = 1

a mod p + b mod p = 8


Remeber this:

(a + b) m = ((a m) + (b m)) m

(a * b) m = ((a m) * (b m)) m


You still have to take modulo of the final result, (a + b) mod is not the same as a mod + b mod, you still need the modulo of the result: (a + b) mod = (a mod + b mod) % mod;


@junior94 >> Time of submission of my answer and your comment differ in few seconds only. :wink: :smiley: I won though, you were late by few seconds. :stuck_out_tongue:

Hehe, I’ll beat you next time… :smiley:

1 Like

Good Luck! :smiley:

1 Like

Something about performance .

fib[0] = 0;

fib[1] = 1;




if(fib[i]>=mod) { 

   fib[i] -= mod; 



This would give best performance . Since each fib before already stored with respect to mod , fib[i-1] + fib[i-2] can be atmax 2*mod-2 . Hence a single subtraction is enough after checking if fib[i-1] + fib[i-2] is >= mod . 

You may not be pressed for performance here , but i have encountered problems in codechef like SPMATRIX in which you get TLE if you use unnecessary use too many % operators 

Please compare the time taken by my code and the code using % . You will see the difference . 

Also , in (a+b)%mod = ( (a%mod) + (b%mod) ) % mod , two mod's are reduntant if a and b have already been stored with respect to mod . Optimizing the number of % operations is key to avoiding TLE in several medium and hard problems .