Pow(x, n)

MathRecursion

MediumLeetCode #50

20 min

Problem Statement

Implement pow(x, n), which calculates x raised to the power n (i.e., xⁿ).

Example

Example 1:

Input: x = 2.00000, n = 10

2¹⁰ = 1024

Output: 1024.00000

Solution (Recursion with Exponentiation by Squaring)

A common and efficient way to solve this problem is by using recursion and the principle of exponentiation by squaring. This avoids the naive approach of multiplying x by itself n times, which would be too slow for large n.

Algorithm Steps

Handle the base cases: if n is 0, return 1.
If n is negative, return 1 / pow(x, -n).
If n is even, we can rewrite xⁿ as (x²)^n/2. Recursively call the function with x*x and n/2.
If n is odd, we can rewrite xⁿ as x * (x²)^(n-1)/2. Recursively call the function for the even part and multiply the result by x.

Current Call

pow(2, 10)

Result

Calculating pow(2, 10)

Pow(x, n) Solution


class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n < 0:
            return 1 / self.myPow(x, -n)
        if n % 2 == 0:
            return self.myPow(x * x, n // 2)
        else:
            return x * self.myPow(x * x, (n - 1) // 2)