Solution For Powx N

The Powx N problem on LeetCode asks us to implement a function that calculates the value of x raised to the power of n. The function takes two parameters x and n as inputs.

There are multiple ways to approach this problem, but one of the most efficient ways is to use the Binary Exponentiation algorithm. Let’s see how it works.

Binary Exponentiation Algorithm

The Binary Exponentiation algorithm is used to find the value of x raised to the power of n in O(log n) time complexity rather than O(n) time complexity achieved by brute force. The algorithm works as follows:

1. Initialize the result variable to 1.
2. While n is greater than 0, do the following:
3. If n is odd, multiply the result by x.
4. Set x to x squared.
5. Divide n by 2.
6. Return the result variable.

This algorithm uses the fact that x^n can be expressed as (x^2)^(n/2) if n is even and x * (x^2)^[(n-1)/2] if n is odd.

Let’s implement this algorithm in Python:

def myPow(x: float, n: int) -> float:
if n == 0:
return 1
if n < 0:
n = -n
x = 1/x
res = 1
while n > 0:
if n % 2 == 1:
res *= x
x *= x
n //= 2
return res

The function takes two parameters x and n and returns the value of x raised to the power of n. We handle the negative value of n by converting it to positive and taking the reciprocal of x.

The while loop runs until n becomes zero and checks if n is odd or even. If n is odd, we multiply res by x, and in the next step, we update the value of x to x squared. If n is even, we update the value of x to x squared, and n is halved.

In this way, we compute the value of x raised to the power of n in logarithmic time complexity.

Time Complexity

The Binary Exponentiation algorithm takes O(log n) time complexity since we keep dividing n by 2 in every iteration of the while loop.

Space Complexity

The space complexity of the solution is O(1) since we use only a few variables to store the intermediate results.

Example

Let’s take an example to understand how the algorithm works. Suppose x = 2 and n = 5. Then, the function should return 32 since 2^5 = 32.

The algorithm works as follows:

1. Initialize res = 1.
2. n is odd (5 % 2 == 1), so multiply res by x (res = 2).
3. Update x to x squared (x = 4).
4. Divide n by 2 (n = 2).
5. Update x to x squared (x = 16).
6. n is even (2 % 2 == 0), so divide n by 2 (n = 1).
7. n is odd (1 % 2 == 1), so multiply res by x (res = 32).
8. Update x to x squared (x = 256).
9. Divide n by 2 (n = 0).
10. Return res (32).

So, the function correctly returns 32 as the value of 2 raised to the power of 5.

Step by Step Implementation For Powx N

public double myPow(double x, int n) {
    
    //if n is 0, return 1
    if(n == 0){
        return 1;
    }
    
    //if n is negative, take the reciprocal
    if(n < 0){
        x = 1/x;
        n = -n;
    }
    
    //if n is even, square the result of x^(n/2)
    if(n%2 == 0){
        return myPow(x*x, n/2);
    }
    
    //if n is odd, multiply the result of x^(n-1) by x
    else{
        return x*myPow(x*x, (n-1)/2);
    }
}

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # if n is 0, the result is always 1
        if n == 0:
            return 1
        # if n is negative, we compute the reciprocal of pow(x, -n)
        elif n < 0:
            return 1 / self.myPow(x, -n)
        # if n is even, we can compute pow(x, n) by squaring pow(x, n/2)
        elif n % 2 == 0:
            return self.myPow(x * x, n / 2)
        # if n is odd, we can compute pow(x, n) by squaring pow(x, (n-1)/2) and multiplying by x
        else:
            return self.myPow(x * x, (n - 1) / 2) * x

//Solution: 

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    //base case
    if(n === 0){
        return 1;
    }
    //recursive case: 
    else if(n < 0){
        return 1/myPow(x, -n);
    }
    else{
        let half = myPow(x, Math.floor(n/2));
        if(n % 2 === 0){
            return half * half;
        }
        else{
            return half * half * x;
        }
    }
};

class Solution {
public:
    double myPow(double x, int n) {
        double res = 1;
        long long p = n;
        if (n < 0) {
            x = 1 / x;
            p = -p;
        }
        while (p) {
            if (p & 1)
                res *= x;
            x *= x;
            p >>= 1;
        }
        return res;
    }
};

public double MyPow(double x, int n) 
{
    //edge case
    if(n==0)
    {
        return 1;
    }
    
    //recursive call
    double result = MyPow(x, n/2);
    
    //if n is even
    if(n%2==0)
    {
        return result*result;
    }
    
    //if n is odd
    else
    {
        if(n>0)
        {
            return result*result*x;
        }
        else
        {
            return result*result/x;
        }
    }
}