LC 50 - Pow(x, n)

Question

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000

Explanation: 2-2 = 1/22 = 1/4 = 0.25

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• n is an integer.
• Either x is not zero or n > 0.
• -104 <= xn <= 104

Links

Question here and solution here

Solution

concept

The main concept here is divide and conquer: if we want to calculate $2^4$, we would calculate $2^2 \times 2^2$, so we keep dividing the power by 2. If the power happens to be odd number then we need to multiply by an extra base: $2^5 = 2^2 \times 2^2 \times 2$.

code

class Solution:
    """
    cheese
    """
    def myPow(self, x: float, n: int) -> float:
        return x**n
        
class Solution:
	"""
	brute force
	TLE
	"""
    def myPow(self, x: float, n: int) -> float:
        if x == 0:
            return 0
        if n == 0:
            return 1

        res = 1
        for i in range(abs(n)):
            res *= x
        return res if n >= 0 else 1 / res
        
class Solution:
	"""
	divide and conquer
	"""
    def myPow(self, x: float, n: int) -> float:
        
        def div_conq(x, n):
	        # base case
            if x == 0:
                return 0
            if n == 0:
                return 1
            
            # keep divide power by 2
            ans = div_conq(x, n//2)
            # multiply the answer by itself
            ans *= ans
            #if power is odd, multiply the base one more time
            if n%2:
                return x*ans
            else:
                return ans
        # only handle pos power first
        ans = div_conq(x, abs(n))
		# 1/ans if power is neg
        return ans if n >= 0 else 1/ans

Complexity

time: $O(\log n)$
space: $O(\log n)$