class Solution:
    '''
    Time Complexity: O(log n)
    Space Complexity: O(log n)
    where, n is the exponent. The stack is only ~31 frames deep at n = 2^31.
    Pitfalls: Normalise the sign once, outside the recursion. Flipping it inside inverts on every level and the inversions cancel in pairs, which is what broke the attempt below.

    Binding half to a variable is the only difference from [divide-conquer-cache] below.
    That is enough to make it O(log n) structurally, so no memoisation is needed.

    Not mine: I had landed on the @cache version below and this came from a suggestion.
    '''
    def myPow(self, x: float, n: int) -> float:
        def dc(x, n):
            if n == 0:
                return 1.0
            half = dc(x, n//2)
            val = half * half
            return val * x if n % 2 else val
        return dc(x, n) if n >= 0 else 1 / dc(x, -n)

class Solution:
    '''
    Time Complexity: O(log n)
    Space Complexity: O(log n)
    Pitfalls: @cache is load-bearing here, not an optimisation. dc(x, n//2) * dc(x, n//2) recomputes the same subtree, so unmemoised it is T(n) = 2T(n/2) + O(1) = O(n): 2,097,151 calls at n = 1e6 versus 21 for the bound-half version, and ~2.1e9 at n = 2^31. Also `if x == 0: return 0` is dead, the recursion already yields 0 for x = 0, n > 0.

    What I got to on my own, and it is accepted. Nothing wrong with @cache, it just hides
    the recursion's real cost behind a decorator; binding half is cleaner.

    How I got here: brute force first, out * x in a loop, O(n) and times out since n goes to
    2^31. Then divide and conquer written from the concept rather than the code, which flipped
    the sign inside the recursion:

        return val if n > 0 else 1 / val

    Every negative frame inverts, so inversions cancel in pairs and the answer is correct or
    reciprocal depending on the parity of the depth. At x = 2: n = -2 gave 0.25 (right),
    n = -4 gave 16.0 (should be 0.0625), n = -16 gave 65536.0 (should be 1.5e-05). The
    ZeroDivisionError at n = -200000000 was the last domino, not the bug: the compounding
    inversions made a frame compute 2^+200000000, which overflows to inf, then 1/inf is 0.0,
    then 1/0.0 raises. It had been silently wrong from n = -4 onward. Lesson: dry run a small
    even and a small odd case before trusting it on the extremes.
    '''
    def myPow(self, x: float, n: int) -> float:
        @cache
        def dc(x, n):
            if x == 0:
                return 0
            if n == 0:
                return 1
            val = dc(x, n//2) * dc(x, n//2)
            return val if n % 2 == 0 else val * x
        return dc(x, n) if n >= 0 else 1 / dc(x, abs(n))