## Solution Approach

### Approach 1: Brute Force Approach

The most straightforward idea is to go by the definition of exponential and multiply a to itself b times. We run a loop for b times and keep multiplying a to answer and taking modulus each time. Also, the answer should be initiated by 1.

### Pseudocode

```
function exponentiation(int a, int b, int m){
int answer = 1;
for(int i=0;i<b;i++){
answer = (answer*a)%m;
}
return answer%m;
}
```

### C++ implementation

```
#include<bits/stdc++.h>
using namespace std;
int exponentiation(int a, int b, int m){
int answer = 1;
for(int i=0;i<b;i++){
answer = (answer*a)%m;
}
return answer%m;
}
int main()
{
int a = 2;
int b = 5;
int m = 1000000;
cout<<exponentiation(a,b)<<endl;
}
```

Output

`32`

Complexity

Time complexity

**O(b)**, where b is the exponent

**Reason**: Since we’re multiplying a to the answer b times using a loop, the time complexity will be O(b). Taking modulus takes constant time.

Space complexity

**O(1)**

**Reason**: All the spaces taken are constant.

### Approach 2: Binary exponentiation

This is the most efficient approach to do modular exponentiation. We need to calculate a^{b}%m, which can also be written as (a^{2})^{b/2}%m. Notice that computing a^{2} takes only constant time, and the whole computation steps are reduced to b/2 steps from b steps. Thus, now we need to calculate x^{b/2}, where x = a^{2}. But, notice that if b is odd, then b/2 will be a decimal, and calculating that is not easy. Also, if b is odd, we can make it even. How? So, x^{b} can be written as x*(x^{b-1}). Thus, whenever we encounter an odd b, multiply x to the answer and reduce the value of b by 1. Then, keep dividing the power by 2 as long as it is even, and keep replacing the base by its square. Keep taking modulus at each step.

### Pseudocode

```
function exponentiation(int a, int b, int m){
int answer = 1;
while(b>0){
if(b%2==1){
answer = (answer*a)%m;
b--;
}
a = (a*a)%m;
b = b/2;
}
return answer%m;
}
```

### C++ implementation

```
#include<bits/stdc++.h>
using namespace std;
int exponentiation(int a, int b){
int answer = 1;
while(b>0){
if(b%2==1){
answer=(answer*a)%m;
b--;
}
a = (a*a)%m;
b = b/2;
}
return answer%m;
}
int main()
{
int a = 2;
int b = 5;
int m = 1000000;
cout<<exponentiation(a,b,m)<<endl;
}
```

Output

`32`

Complexities

Time complexity

**O(log**_{2}b), where b is the exponent

**Reason**: Since we’re dividing b by 2 in each step, the total number of steps will be log_{2}b. Taking modulus takes constant time.

#### Space complexity

**O(1)**

**Reason**: All the spaces taken are constant.

Check out this problem - __Maximum Product Subarray__

## Frequently asked questions

**What is modular exponentiation method?**

Exponentiation is a mathematical operation written as a^{b}, which means the value a is multiplied by itself b times.

**What is the time complexity of the binary exponentiation method?**

The time complexity of the binary exponentiation method is log(b), where b is the exponent.

**What should we do if an exponentiation's value is too large to fit in the integer range?**

If any answer's value is so large that it can’t fit in the integer range, take its modulo with a prime number. Generally, that prime number is 10^9 + 7.

**What is modulo?**

Modulo represents the remainder when a number a is divided by another number b.

**Where can binary exponentiation be used?**

Binary exponentiation can efficiently compute Fibonacci numbers and apply a permutation on an array k times.

## Conclusion

This article discussed the approach to solving “Modular exponentiation.” This was a basic problem of number theory. You should solve some more number theory problems to have a good grasp of this topic. Some of these are: __number of vehicles__, __Yogesh and primes__, __alien dictionary__, __nth Fibonacci number__, __jumping numbers__, __minimum jumps__, and __stocks are profitable__.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more?

Attempt our __Online Mock Test Series__ on__ ____Coding Ninjas Studio__** **now!

**Happy Coding!**