50. Pow(x, n)

# Divide and conquer approach
# intuition: x^(2n) = (x^n)^2
# i.e. x^(N) = (x^(N/2))^2 if N is even
# if the exponent is odd, lets say N = 2M+1, then x^(N) = (x^M)^2 * x

# TC: log(n)
# SC: log(n) from recursion stacks

class Solution:
    def myPow(self, x: float, n: int) -> float:

        def fastPow(x: float, n: int) -> float:
            if n == 0:
                return 1.0

            half = fastPow(x, n // 2) # floor divide will leave 1 out if n is odd
            if n % 2 == 0:
                return half * half

            return half * half * x # if n is odd, multiply by x again

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

        return fastPow(x, n)