Modular exponentiation doubt?

#1

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 my code is https://ide.codingblocks.com/s/104595

#2

Hello @ejazsaifi70,

There are multiple issues with your program:

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

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

  3. You are not considering one important base case i.e. power of 0 is always 1.

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