Implement integer exponentiation. That is, implement the pow(x, y)
function, where x
and y
are integers and returns x^y
.
Do this faster than the naive method of repeated multiplication.
For example, pow(2, 10)
should return 1024.
Example:
Input: a= 2, n=10
Output: 1024
Approach 1: Naive
C++
#include <bits/stdc++.h>using namespace std;int binpower(int a, int b){int res = 1;for (int i = 1; i <= b; i++){res = res * a;}return res;}int main(){int a = 2, n = 10;cout << binpower(a, n);return 0;}//Time Complexity : O(n)
Approach 2: Efficient (Iterative)
C++
#include <bits/stdc++.h>using namespace std;long long int binpower(long long int a,long long int b){long long int res=1;while(b){if(b&1)res=res*a;a=a*a;b>>=1;}return res;}int main(){long long int a=2,n=10;cout<<binpower(a,n)<<"\n";return 0;}//Time Complexity : O(log(n))
Approach 3: Efficient (Recursive)
C++
#include <bits/stdc++.h>using namespace std;long long int binpower(long long int a,long long int n){if(n==0)return 1;long long int res=binpower(a,n/2);if(n&1)return res*res*a;elsereturn res*res;}int main(){long long int a=2,n=10;cout<<binpower(a,n)<<"\n";return 0;}//Time Complexity : O(log(n))
No comments:
Post a Comment