Modular Exponential

#1

A few test cases are failing please check my code

#2

Hi Rachit … U might be getting a wa due to fact that intermediate values of ans can also overflow the integer value.
ans%=c;
Try to add this after every iteration.

1 Like
#3

Why is it correct to do so? I mean it works now. Can you explain mathematically?

#4

Well see
Let a= 10^18( Fits inside long long)
let b= 10^18(This too fits inside long long)

Now let c=axb
even if we declare data type of c as long long it will over flow right
since c=10^36
Now even if u do c=c%1000000000
It doesn’t matter because it has already overlowed outside long long range due to multiplication.

But if we do c=((a%MOD)*(b%MOD))%MOD
Let MOD=10^9
Now a and b both will become less than 10^9 and their product also will be less than or equal to 10^18.
So as to avoid overflow during in between calculations we have to use %MOD.

1 Like