Confusion regarding modulo operaor

Referring to this solution http://www.codechef.com/viewsolution/3331816 (got AC) for the question http://www.codechef.com/problems/CLMBSTRS, i came across teh confusion regarding modulo operator.
I initially framed the array fib[] this way

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

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

3 Likes

Remeber this:

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

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

4 Likes

Something about performance .

fib[0] = 0;

fib[1] = 1;

for(i=2;i<=MAX;i++)

{ 

fib[i]=fib[i-1]+fib[i-2]; 

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 .
3 Likes

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;

2 Likes

@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