C++ O(logN) solution!


#1

#define ll long long
ll power(ll A,ll B,ll C)
{
if(B==0)
{
return 1;
}
else if(B%2==0)
{
return (power(A,B/2,C) * power(A,B/2,C))%C;
}
else
{
return (A * power(A,B-1,C))%C;
}
}
int Solution::Mod(int A, int B, int C) {
if(A==0) return 0;
if(A<0)
{
A=(A%C+C)%C;
}
return power(A,B,C);

}


#2

Can u please explain the time complexity calculation.


#3

@himsindhu-biswas,

Can we not just do A = A + C instead of A=(A%C+C)%C; ?


#4

I don’t think there is anything wrong in doing A = A+C as well…maybe those extra %C were for safety
# define ll long long
ll power(ll A, ll B, ll C){
if(B == 0) return 1;
else if(B%2 == 0){
ll y = power(A, B/2, C);
return (y*y) % C;
// return (power(A,B/2,C) * power(A,B/2,C))%C; (also correct)
}
else return ((A%C) * power(A, B-1, C)) % C;
// else return (A * power(A,B-1,C))%C; (also correct)
}

int Solution::Mod(int A, int B, int C) {
    if(A == 0) return 0;
    // if(A < 0) A = A+C; (also correct)
    if(A < 0) A = (A%C+C) % C;
    
    return power(A,B,C);
}