Question

Implement pow(x, n), which calculates x raised to the power n (\(x^n\)).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

• \[-100.0 < x < 100.0\]
• n is a 32-bit signed integer, within the range \([−2^{31}, 2^{31} − 1]\)

Solution

class Solution:
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1
        if n == 1:
            return x
        if x == 0:
            return 0

        positive = True if n > 0 else False
        n = -1 * n if n < 0 else n
        dp = []
        dp.append((1, x if positive else 1/x))

        i = 2
        while i <= n:
            prev = dp[-1]
            dp.append((i, prev[1] * prev[1]))
            i *= 2

        last = len(dp) - 1
        res = dp[last][1]
        n -= dp[last][0]

        while n > 0:
            for idx in range(last - 1, -1, -1):
                power = dp[idx][0]
                if power <= n:
                    last = idx
                    break

            res *= dp[last][1]
            n -= dp[last][0]

        return res