Exponentiation With Modulus Editorial

Practice Problem Link: Exponentiation With Modulus | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given three numbers x, y, and z, Calculate (x^y) % z.

Naive Approach

We can multiply x with itself y times, and keep taking modulo at every step. Return the result after that.

Analysis

• Time Complexity: O(y)
• Space Complexity: O(1)

Implementation

C++

int getModulatedPower(int x, int y, int z) {
   int value = x;
    for(int i = 1; i <= y; i++) {
       x = (x * value) % z;
   }
   return x;
}

Java

class Solution {
   int getModulatedPower(int x, int y, int z) {
       int value = x;
       for(int i = 1; i <= y; i++) {
           x = (x * value) % z;
       }
       return x;
   }
}

Optimal Approach

We can solve this problem in logarithmic time.

Logic:

• If y = 0, we return one.
• Else if y is even, we can write the equation as x^{(y / 2) * 2}.
• Else if y is odd we can write it as x^{((y  - 1) / 2) * 2} * x.

We can run this algorithm till it converges into the base case. Since y has at the most floor(log y) + 1 bits, the effective complexity of the algorithm will be logarithmic.

Analysis

• Time Complexity: O(log y)
• Space Complexity: O(1)

Implementation

C++

int power(int x, int y, int z) {
   int result = 1;
   x %= z;
   if(x == 0) {
       return 0;
   }
   while(y > 0) {
       if(y % 2 != 0) {
           result = (result * x) % z;
       }
       y /= 2;
       x = (x * x) % z;
   }
   return result;
}
int getModulatedPower(int x, int y, int z) {
   return power(x, y, z);
}

Java

class Solution {
   int power(int x, int y, int z) {
       int result = 1;
       x %= z;
       if(x == 0) {
           return 0;
       }
       while(y > 0) {
           if(y % 2 != 0) {
               result = (result * x) % z;
           }
           y /= 2;
           x = (x * x) % z;
       }
       return result;
   }
   int getModulatedPower(int x, int y, int z) {
       return power(x, y, z);
   }
}