# 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