Pow(x, n)

01 · Question

Compute x raised to integer exponent n using fast exponentiation. For n<0, x must be nonzero; for n=0 return 1.

Examples: x=2, n=10 → 1024; x=2, n=−2 → 0.25; x=−2, n=3 → −8. Results use floating-point arithmetic.

02 · Analysis

Compute the half-power once, square it, and account for one extra x when the exponent is odd. Reusing half gives O(log(|n|+1)) time and stack space, with O(1) cost at n=0.

Python converts a negative exponent using the reciprocal base; its integer negation does not overflow. Go instead divides the signed exponent toward zero and divides the odd result by x for negative n. This avoids negating the minimum representable int, which cannot be represented as a positive int. Floating-point rounding, overflow, and underflow still apply.

03 · Solution

Reference solution

1def myPow(x: float, n: int) -> float:
2    if n < 0:
3        x, n = 1.0 / x, -n
4    def visit(exponent):
5        if exponent == 0:
6            return 1.0
7        half = visit(exponent // 2)
8        result = half * half
9        return result * x if exponent % 2 else result
10    return visit(n)

Fibonacci Number

Reverse String