50. Pow(x, n) (Math, Recursion)

링크 - https://leetcode.com/problems/powx-n/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) Binary Exponentiation (Recursive)

2^10인 경우를 보자. 이는 (2^2)^5 = 4^5로 변환 가능하다. 또한 이는 (4^2)^2 * 4로 변환가능하다.

즉 n을 2로 계속 나누면서 나온 결과를 곱하면 되는 것이다. n이 짝수이면 x = x*x로 하면 되고, n이 홀수이면 x = x*x로 하되, rem이라는 변수를 따로 줘서 거기에 x를 곱해준다. 그리고 맨 마지막에 rem을 곱해주면 된다.

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)

Time Complexity: O(logn)

Space Complexity: O(logn)

2) Binary Exponentiation (Iterative)

방식은 Recursive와 같다. 하지만 while문을 사용하여 n을 계속 나눠가는걸로 하여 space complexity를 O(1)로 하는것에 의의를 둔다.

class Solution:
    def myPow(self, x: float, n: int) -> float:
        ans = x
        rem = 1
        is_pos = n > 0
        n = abs(n)

        if x == 1 or x == 0:
            return x

        if n == 0:
            return 1

        while n > 1:
            if n % 2 == 1:
                rem *= x
            n //= 2
            x = x*x
        return x * rem if is_pos else 1 / (x * rem)

Time Complexity: O(logn)

Space Complexity: O(1)