Facto Sum problem test cases not passed

#1

#include<stdio.h>
int factorial(int n){
int r=1;
for(int i=1;i<=n;i++){
r=r*i;
}
return r;
}
int main() {
int n,sum=0,t=0;
scanf("%d",&n);

while(n–){
scanf("%d",&t);
sum=sum+factorial(t);
}
printf("%d",sum%107);
return 0;
}

#2

When you multiply or add lot of numbers, the ‘int’ overflows.
It means when you cross the max int value, a wrap around occurs and numbers become negative.

Try computing 20! or any large factorial, you will start seeing -ve answers.
To avoid this problem we take modulo at every step using modulo properties

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

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

So your code will have some changes like -
r=(r*i)%m

return r%m

sum = (sum + factorial(t)) %m

So take modulo at very step wherever you are doing multiplication or addition.

3 Likes