Pow(x, n)

Medium Subject: Math & Geometry

Time Complexity

O(log N)

Space Complexity

O(1)

Problem Description

Problem Statement

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

Example 1:

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

Optimal Solution

Python

Approach: Binary Exponentiation

To optimize, we use binary exponentiation. If n is even, x^n = (x^2)^(n/2). If n is odd, x^n = x * x^(n-1). We handle negative n by taking the reciprocal of x. This reduces the time complexity to O(log N).

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

        res = 1
        while n:
            if n % 2 == 1:
                res *= x
            x *= x
            n //= 2

        return res