LeetCode 50: Powx N — Step-by-Step Visual Trace

#leetcode #algorithms #python

Medium — Math | Recursion | Divide and Conquer

The Problem

Implement a function to calculate x raised to the power n (x^n) efficiently. The function should handle both positive and negative exponents and return the result as a floating-point number.

Approach

Uses fast exponentiation (exponentiation by squaring) with recursion to reduce time complexity. For negative exponents, it converts x to 1/x and makes n positive, then applies the recursive helper that squares intermediate results to minimize multiplications.

Time: O(log n) · Space: O(log n)

Code

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def helper(base, exp):
            if exp == 0:
                return 1.0
            temp = helper(base, exp // 2)
            if exp % 2 == 0:
                return temp * temp
            else:
                return base * temp * temp

        if n < 0:
            x = 1 / x
            n = -n

        return helper(x, n)