Pow (x, n)

# editorial sol
class Solution:
    def binaryExp(self, x: float, n: int) -> float:
        # Base case, to stop recursive calls.
        if n == 0:
            return 1

        # Handle case where, n < 0.
        if n < 0:
            return 1.0 / self.binaryExp(x, -1 * n)

        # Perform Binary Exponentiation.
        # If 'n' is odd we perform Binary Exponentiation on 'n - 1' and multiply result with 'x'.
        if n % 2 == 1:
            return x * self.binaryExp(x * x, (n - 1) // 2)
        # Otherwise we calculate result by performing Binary Exponentiation on 'n'.
        else:
            return self.binaryExp(x * x, n // 2)

    def myPow(self, x: float, n: int) -> float:
        return self.binaryExp(x, n)

# my sol
class Solution:
    def myPow(self, x: float, n: int) -> float:
        # instead of reducing exponent n by 1
        # at each recursive call we will reduce by half
        if n == 0:
            return 1.0
        if n < 0:
            return 1.0/self.myPow(x, -n)

        if n%2 == 0:
            return self.myPow(x*x, n/2)
        else:
            return x*self.myPow(x*x, n//2)