Modular arithmetic help

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.

  1. 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).

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

  3. Sorry about missing MOD in square(), it was unintentional.

In both case 1(f=f * (i%MOD):wink: 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