Powx N - Leetcode Solution

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:
   • If n is odd, multiply the result by x.
   • Set x to x squared.
   • Divide n by 2.
3. 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.

1