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(1)
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(1)
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