[LeetCode] 050. Pow(x, n)

• Problem (Medium)
• Approach 1: (My Solution 41.86%) Use the Binary of n
  • Idea
  • Solution
  • Complexity

Problem (Medium)

050. Pow(x, n)

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]

Approach 1: (My Solution 41.86%) Use the Binary of n

Idea

The purpose of this problem to try to find better ways to save computation in the possible multplication loops. My strategy:

• Convert the n to binary. e.g. n=10 -> 0b1010;
• Thus, pow(2, 10) equals to (2x2)^3 * (2x2)^1;

Solution

class Solution1:
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        def square(x, n):
            res = x
            while(n):
                res = res*res
                n -= 1
            return res

        res = 1.0
        for i, c in enumerate(bin(abs(n))[-1:1:-1]):
            if c == '1':
                res *= square(x, i)
        if n < 0:
            return 1 / res
        return res

Complexity

• Time: $O()$?
• Space: $O()$?

KF