All suggestions are welcome. Please upvote if you like it. Thank you.
Leetcode Problem Link: 50. Pow(x, n)
Brute Force Solution:
class Solution {
public:
double myPow(double x, int n) {
// Brute Force Solution Time O(N) & Auxiliary Space O(N)
if(n==0)
return 1;
else if(n>0)
return x*myPow(x,n-1);
else
return (1/x)*myPow(x,n+1);
}
};
Efficient Solution:
class Solution {
public:
double myPow(double x, int n) {
// Optimal Solution Time O(logN) & Auxiliary Space O(logN)
if(n==0)
return 1;
// Using Binary Exponentiation(Time O(logN))
// x^n=x^(n/2)*x^(n/2). So, recursive function is
// called logN times where y=x^(n/2) and function returns y*y
double y = myPow(x,n/2);
if(n%2==0)
return y*y;
else if(n < 0)
return 1/x*y*y;
else
return x*y*y;
}
};
All suggestions are welcome. Please upvote if you like it. Thank you.
Top comments (0)