leetcode: 50. Pow(x, n)

# Implement pow(x, n).
#
# Example 1:
#
# Input: 2.00000, 10
# Output: 1024.00000
# Example 2:
#
# Input: 2.10000, 3
# Output: 9.26100

要考虑到 n 为负 的情况。

# time: O(log n)
class Solution():
    def myPow(self, x, n):
        if n == 0:
            return 1
        else:
            m = self.myPow(x, abs(n)//2)
            res = m * m * x if abs(n) % 2 else m * m
            res = 1.0/res if n < 0 else res
            return res


if __name__ == "__main__":
    assert Solution().myPow(3, 5) == 243