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?
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.
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.