50. Pow(x, n)

This is the classic fast exponentation algorithm. We take care of the base cases, where if the power is 0, we return 1, or if it is 1, we return the number.

If the power is of even parity, we want to multiply x by itself and divide n by 2. If it is of odd parity, we do the same but multiply the spare x with the result and return that.

To handle negative numbers I also take care by doing 1 / res.

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def fast_pow(x, n):
            if n == 0: 
                return 1
            if n == 1:
                return x
            res = fast_pow(x * x, n // 2)
			if x % 2 == 1:
				res *= x
            return res
        
        res = fast_pow(x, abs(n))
        if n < 0:
            return 1 / res
        return res