Can somebody tell me how to use modular arithmetic in C programming? Every time I make some mistakes and am unable to find the error. My approach seems right but modular arithmetic part isn’t.
I have tried some programs and got success in very few (two or three only). Also they had only addition and subtraction problem. When it comes to division, I am out of knowledge.
The last problem I tried was this and my approach is same as that in editorial. But I am getting wrong answer in all test cases except the sample ones. Can you please check my code and rectify my error?
My code
I have rectified the error in your code and here is the link to accepted solution.
Go through it and you will find out where you were wrong.
1 Like
Thank you. That was really helpful. But I still have a few doubts though.
-
While computing factorial, why isn’t the calculation f=(f*(i%MOD))%MOD. I mean in each successive terms, you are multiplying f%MOD to i. (I know i<MOD, so it doesn’t matter here, but would it matter if i>MOD).
-
Again, in main function, we are finding MOD in each multiplication (as den=(den*(fact(arr[i])))%MOD;) Shouldn’t fact() function return the value already modulated?
-
Sorry about missing MOD in square(), it was unintentional.
In both case 1(f=f * (i%MOD)
and 2(den=den * (fact(arr[i]));), what you were doing was wrong.
When you do f=f * (i%MOD); then you are taking MOD of only “i” but not of the whole expression. So suppose when this expression evaluates for i=1 to 50, the value of f will be 1 * 2 * 3 * 4…48 * 49 * 50 while if you make a small change in it i.e. f=(f * i)%MOD then value of f will be
(…(((1 * 2)%MOD) * 3)%MOD) * 4)%MOD)… * 49)%MOD) * 50)%MOD.
I hope you understand this.
The same is applicable on case 2, you have to take MOD in each step after multiplication of ‘den’ and ‘fact’.
Yes, I think I got it. Thanks alot bro.
1 Like