Data Structure / Maths

Calculate the Power of a Number : Binary Exponentiation

Problem Statement: Find the Power of a number.

Examples:

Example 1:
Input: N = 5, k=3
Output: 125
Explanation: Since 5*5*5 is 125.

Example 2:
Input: n=2 k=4
Output: 16
Explanation: Since 2*2*2*2 is 16

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Naive approach

Intuition: Simply multiply n for k times.

Approach:

  • Take a variable ans to store final answer.Initially let the value of ans be 1.
  •  Multiply ans with n for k times.
  • Print ans.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n = 5, k = 3;
	int ans = 1;
	for (int i = 0; i < k; i++) {
		ans = ans * n;
	}
	cout <<n<<" raised to the power "<<k<<" is "<< ans;
}

Output:

5 raised to the power 3 is 125

Time Complexity: O(k).

Space Complexity: O(1)

Java Code

public class Main {
  public static void main(String args[]) {
    int n = 5, k = 3;
    int ans = 1;
    for (int i = 0; i < k; i++) {
      ans = ans * n;
    }
    System.out.print(n+" raised to the power "+k+" is "+ans);
  }
}

Output:

5 raised to the power 3 is 125

Time Complexity: O(k).

Space Complexity: O(1)

Solution 2: Binary exponentiation.

Intuition: While calculating (n^k), binary exponentiation relies on whether n is even or odd.

If k is even (nk) can be written as  (n2)k/2. As we can see that computation steps were reduced from k to k/2 in just one step.

If k is odd (nk) can be written as n.(n)k-1, so now  (k-1) is even.

Approach:

  • Maintain a variable ans to store the final answer.
  • If k is even,square n and divide k by 2.as nk can be written as (n2)k/2  i.e (n*n)k/2.
  • If k is odd,multiply ans with n and reduce k by 1,as nk can be written as n*(n)k-1.
  • Print the ans.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n = 2, k = 3;
	int num=n,kk=k;
	int ans = 1;
	while (k != 0) {
		if (k % 2 == 0) {
			n = n * n;
			k /= 2;
		}
		else {
			ans = ans * n;
			k--;
		}
	}

	cout <<num<<" raised to the power "<<kk<<" is "<< ans;
}

Output:

2 raised to the power 3 is 8

Time Complexity: O(logn).

Space Complexity: O(1)

Java Code

public class Main {
  public static void main(String args[]) {
    int n = 2, k = 3;
    int num=n,kk=k;
    int ans = 1;
    while (k != 0) {
      if (k % 2 == 0) {
        n = n * n;
        k /= 2;
      } else {
        ans = ans * n;
        k--;
      }
    }

    System.out.print(num+" raised to the power "+kk+" is "+ans);
  }
}

Output:

2 raised to the power 3 is 8

Time Complexity: O(logn).

Space Complexity: O(1)

Solution 3: Using library function

For c++: pow(n,k)

For java: Math.pow(n,k);

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n = 2, k = 3;
	int ans=pow(n,k);

	cout <<n<<" raised to the power "<<k<<" is "<< ans;
}

Output:

2 raised to the power 3 is 8

Time Complexity: O(log n)

Space Complexity: O(1)

Java Code

public class Main {
  public static void main(String args[]) {
    double n = 2, k = 3;
    double ans=Math.pow(n,k);

    System.out.print(n+" raised to the power "+k+" is "+ans);
  }
}

Output:

2.0 raised to the power 3.0 is 8.0

Time Complexity: O(log n)

Space Complexity: O(1)

Special thanks to Pranav Padawe for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article