Modular Exponentiation - Wrong Answer

#1

My solution is https://ide.codingblocks.com/s/181251.
Please see to it. I

#2

Hey @adarsh_anand pow(a, b) can overflow long long int that why you are getting wrong answer. Please refer to code snippet given below for modular exponentiation

int power(int x, unsigned int y, int p) 
{ 
    int res = 1;      // Initialize result 
  
    x = x % p;  // Update x if it is more than or  
                // equal to p 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % p; 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % p;   
    } 
    return res; 
}
1 Like
#3

I also tried to write the power function recursively and I still wasn’t able to clear all the test cases. Can you explain why?

#4

Make sure you have replaced int with long long int this was just reference code so if x, y, p are big it’ll fail