Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
Approach 1: Brute Force
3.1.1.
Pseudocode:
3.1.2.
C++ implementation
3.1.3.
Java Implementation
3.1.4.
Python Implementation
3.1.5.
Complexity
3.2.
Approach 2: Binary exponentiation
3.2.1.
Pseudo - code:
3.2.2.
C++ implementation
3.2.3.
Java Implementation
3.2.4.
Python Implementation
3.2.5.
Complexities
3.2.6.
Space complexity
4.
Frequently asked questions
5.
Key Takeaways
Last Updated: Mar 27, 2024

Binary Exponentiation

Author Shreya Deep
0 upvote
gp-icon
Competitive programming
Free guided path
16 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Exponentiation is a mathematical operation written as ab, which means the value when a is multiplied by itself b times. Here, a is called the base, and b is called the exponent or the power.

This article describes methods of doing exponentiations. 

Problem Statement

Given a number a and another number b, compute a^b.

For example,

Input

a  = 2, b = 14

Output

16384

Explanation: Multiplying 2 to itself 14 times gives 16384.

Also see, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution Approach

Approach 1: Brute Force

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. Also, the answer should be initiated by 1. 

Pseudocode:

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

C++ implementation

#include<bits/stdc++.h>
using namespace std;

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

int main()
{
    int a = 2;
    int b = 14;
    cout<<exponentiation(a,b)<<endl;
}

Java Implementation

public class Main
{
   public static int exponentiation(int a, int b){
       int answer = 1;
       for(int i=0;i<b;i++){
           answer = answer*a;
       }
       return answer;
   }
public static void main(String[] args) {
    int a = 2;
       int b = 14;
 System.out.println(exponentiation(a,b));
}
}

Python Implementation

def exponentiation(a, b):
   answer = 1
   for i in range(b):
       answer *= a
       
   return answer
   
a = 2
b = 14
print(exponentiation(a, b))

Output

16384

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

Space complexity

O(1)

Reason: All the spaces taken are constant.

Approach 2: Binary exponentiation

This is the most efficient approach to do exponentiation. We need to calculate ab, which can also be written as (a2)b/2. Notice that computing a2 takes only constant time, and the whole computation steps are reduced to b/2 steps from b steps. Thus, now we need to calculate xb/2, where x  = a2. 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, xb can be written as x*(xb-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. 

Let’s analyze the difference between the above two approaches for an example. 

Assume a = 2, b = 30.

  • The number of steps taken by approach 1 is 30.
  • The number of steps taken by approach 2 is 4, equal to log2(30).

Thus, we can see that the second approach is very efficient. 

Pseudo - code:

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

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*=a;
            b--;
        }
        a = a*a;
        b = b/2;
    }
    return answer;
}

int main()
{
    int a = 2;
    int b = 14;
    cout<<exponentiation(a,b)<<endl;
}

Java Implementation

public class Main
{
   public static int exponentiation(int a, int b){
   int answer = 1;
   while(b>0){
       if(b%2==1){
           answer*=a;
           b--;
       }
       a = a*a;
       b = b/2;
   }
   return answer;
   }
public static void main(String[] args) {
    int a = 2;
       int b = 14;
 System.out.println(exponentiation(a,b));
}
}

Python Implementation

def exponentiation(a, b):
   answer = 1
   while b > 0:
       if b%2==1:
           answer *= a
           b -= 1
           
       a *= a
       b //= 2
       
   return answer
   
a = 2
b = 14
print(exponentiation(a, b))

Output

16384

Complexities

Time complexity

O(log2b), where b is the exponent

Reason: Since we’re dividing b by 2 in each step, the total number of steps will be log2b.

Space complexity

O(1)

Reason: All the spaces taken are constant.

 

Must read decimal to binary c++ 

Frequently asked questions

  1. What is exponentiation?
    Exponentiation is a mathematical operation written as ab, which means the value a is multiplied by itself b times.
     
  2. 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. 
     
  3. Can exponentiation be done in O(logn) time?
    Yes, exponentiation can be done in O(logn) time.
     
  4. 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.
     
  5. Where can binary exponentiation be used?
    Binary exponentiation can efficiently compute Fibonacci numbers and apply a permutation on an array k times.

Key Takeaways

This article discussed the method of doing binary exponentiation. These mathematical concepts are used to make our solutions faster. You can read and learn more mathematical concepts here

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!

Previous article
Modular Arithmetic
Next article
Extended Euclidean Algorithm
Guided path
Free
gridgp-icon
Competitive programming
16 chapters
217+ Problems
gp-badge
Earn badges and level up
Live masterclass