Question : You are given two integers , write a function to calculate x^n . Example : x=2 , n=`10 . 2^10=1024
Brute Solution :
You can loop from1 to n and you can keep a variable ans and every time you loop you can multiply x .So basically idea is , multiply x , n times.
Pseudo Code :
for(1 to n){
ans*=x;
}
Edge case : if n is negative ;
then ; x^(-n)=1/x^n
so you have to return 1/ans instead of only ans .
Here you need to take long or long long instead of int to overcome overflow.
Time complexity : O(n)
Space complexity : O(1)
Optimal Solution :
To get the optimal solution lets go through an example :
Steps :
i) 2^10 = (2 x 2)^5 =4^5
ii) 4^5 = 4 x 4^4
iii) 4^4 = (4 x 4)^2 = 16^2
iv) 16^2 = (16 x 16)^1 = 256^1
v) 256 = 256 x 256^0
Now we are finding , 4^4 from third step which we found as 256 .
So now our second step can be rewritten as :
ii) 4 x 256 = 1024
Now step first step can be written as :
2^10=4^5=1024
So we observed over here whenever the power was even we did multiply the x into x and we divided the n by two and when ever the n was odd we multiplied the answer with x and we reduced n by one and ultimately whenever our n was zero we stopped.
Cases :
i) n%2 == 0 then x = x*x and n = n/2
ii)n%2 == 1 then n = n-1 and ans*=x
Code :
C++
function to calculate x^n :
double myPow(double x, int n) {
double ans=1.0;
long nn=n;
if(n<0) nn=-1*nn;
while(nn>0)
{
if(nn%2==1)
{
ans=ans*x;
nn=nn-1;
}
else
{
x=x*x;
nn=nn/2;
}
}
if(n<0)ans=(double)1.0/(double)ans;
return ans;
}
};
Time Complexity : O (log n)
Space complexity : O(1)
Leave a Reply