what is the wrong in my code , one of the test case failed that is 56789 3452 100000 . my code print 369 but answer is 57521
Modular exponentiation doubt ///
I have already replied to you on that thread.
But i am sending it here also.
Hello @ejazsaifi70,
There are multiple issues with your program:
The logic you are applying for even and odd number is wrong. It should be as:
The idea is based on below properties.
Property 1:
(a * b) % c has a very interesting property:
(a * b) % c =((a % c) * (b % c)) % c
Property 2:
if b is even:
y = (a ^ b) % c = (a ^ (b/2 + b/2) % c) = ((a ^ b/2) * (a ^ b/2))%c
if b is odd:
y = (a ^ b) % c = (a^(b-1+1) %c) = (a * (a ^( b-1))%c
You are not considering the negative numbers
Property 3:
If we have to return the mod of a negative number y whose absolute value is less than c:
then (y + c) % c will do the trick
You are not considering one important base case i.e. power of 0 is always 1.
The product of two int can be a long value also. Thus you have to use long datatype.
I have modified your code, you can check it here.
Hope, it will help.
Give a like if you are satisfied.