I have a stupid doubt if in question we have given range of values upto 10^18 but the answer is accepted to be MODULO 10^9 + 7.
Then i have two choices:
- At each step i should take MODULO, despite the fact that number can be stored in long long int range.(shown by fun1)
- I should take MODULO only where the result is excepted to overflow range of data type.(shown by fun2)
which approach is correct and why ?
ll:long long int
ex:
void fun1(ll a,ll b)
{
a=a%M;
b=b%M;
ll c=(a+b)%M;
ll d=(c*a)%M;
cout<<d<<endl;
}
void fun2(ll a,ll b)
{
ll c=(a+b)%M;
ll d=(c*a)%M;
cout<<d<<endl;
}
fun1 is safer if a and b are of order 10^18,
Here’s how fun2 fails,
fun2(10^18,10^18)
c=~10^9
d=((10^9)(10^18))%MOD, overflow here! (better use ((c%M)(a%M))%M )
Nope one of them is not correct
If a and b are less than M i.e. a, b \leq 10^9+6 then a+b \leq (10^9+6)\cdot 2 and a*b \leq (10^9+6)^2 \sim 10^{18} therefore(a+b)%M
and (a*b)%M
will be correct and efficient. Modulo is a ‘heavy’ operation so use it as less as possible.
Usually, what we want to calculate is in terms of previously calculated ( and modulo’d ) elements. For example if you want to calculate the factorial of a number n, you can do
fact[0] = 1
for( ll i=1; i<=n; ++i )
fact[i] = (i*fact[i-1])%m;
Notice we did not have to do fact[i] = ((i%m)*(fact[i-1]%m))%m;
1 Like
Bcuz you know that fact[i-1] < m and i<m so there is no point of taking mod again. So in your functions as well if you are sure that a and b are less than m then no need for mod.