DAY 51 - Power of a Number n

Hey everyone! Welcome back to another day of problem-solving. It's day 51, and I'm still going strong on my quest for consistency.
Today and we will be solving the daily leetcode problem.

Question: Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (x^n).

Example 1:

• Input: x = 2.00000, n = 10
• Output: 1024.00000

Example 2:

• Input: x = 2.00000, n = -2
• Output: 0.25000
• Explanation: 2-2 = 1/22 = 1/4 = 0.25

Intuition:

• Now I don't think the question needs a break down today so let's head right down to thinking how to approach this problem.
• We need to find x ^ n.
• This can also be written as (x ^ n/2) * (x ^ n/2)
• Due to the additive property of powers when two same numbers are multiplied we can break it down into two problems.
• Similarly we can break down these problems further and reach to a simple answer that we all know.
• Anything to the power 0 is 1.
• Any number to the power 1 is itself.
• We are following a recursive approach so let's now write down the code for this.

Algorithm:

Establishment of base cases.

• If n == 0 return 1.
• If n == 1 return x;

Recursive Call:

• Ans = pow(x,n/2).
• If n is even(perfectly divisble by 2) we return ans * ans.
• if n is odd we return x * ans * ans.
• Else if n is negative we return 1 / pow(x,-n).

Returning the ans

• The recursive function itself returns the answer here.

Code:

double myPow(double x, int n){
            if(n==0){
            return 1;
            }
            if(n==1){
                return x;
            }
            double ans = myPow(x, n/2);
            if(n%2==0)
                return ans*ans;
            else if(n%2 == 1) 
                return x*ans * ans;
            else
//                 is loop me tb jayega jb n negative hoga, or, is loop me ek hi baar jayega because isme negative wale ko positive kr rhe h, to agr koi negative hoga, to ye loop sirf ek hi baar call hoga
// this loop will only be entered if n is negative. After that it's made positive and this loop will never be called again.

                return 1/myPow(x,-n);
    }

Complexity Analysis:

Time: O(logN)
Space: O(1)