50. Pow(x, n)

Description

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

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/2² = 1/4 = 0.25

Constraints:

• -100.0 < x < 100.0
• -2³¹ <= n <= 2³¹-1
• n is an integer.
• Either x is not zero or n > 0.
• -10⁴ <= xⁿ <= 10⁴

Submitted Code

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0:  return 0
        
        res = 1.0
        if n < 0:           # 지수가 음수일 경우
            x = 1 / x
            n = -n

        while n > 0:
            if n % 2 == 1:  # 지수를 다시 짝수로 변경(마지막 지수가 1일 때도 적용)
                res *= x
            x *= x          # x를 제곱
            n //= 2         # 지수를 절반으로 줄임

        return res

Runtime: 0 ms | Beats 100.00%
Memory: 19.54 MB | Beats 35.24%

n의 범위가 크기 때문에 x를 n번 그대로 곱하면 시간 초과가 발생한다. n이 짝수일 때 x를 제곱하는 것으로 연산 횟수를 줄일 수 있다. n //= 2 대신 n >>= 1으로 비트 연산해도 같은 결과가 나온다.

Other Solutions

1st

class Solution:
    def myPow(self, x: float, n: int) -> float:

        def calc_power(x, n):
            if x == 0:
                return 0
            if n == 0:
                return 1
            
            res = calc_power(x, n // 2)
            res = res * res

            if n % 2 == 1:
                return res * x
            return res

        ans = calc_power(x, abs(n))

        if n >= 0:
            return ans
        return 1 / ans

time complexity: 𝑂(log𝑛)
space complexity: 𝑂(log𝑛)

재귀로 푸는 방법도 참고했다.