Pow(x,n) | You are given two integers , write a function to calculate x^n .




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)



Partner Sites

VideoToGifs.com

EasyOnlineConverter.com

SqliteTutorials.com





Be the first to comment

Leave a Reply

Your email address will not be published.


*