 # 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

fib = 0;

fib = 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.  I won though, you were late by few seconds. Hehe, I’ll beat you next time… 1 Like

Good Luck! 1 Like