Pow(x, n)

LeetCode 50. Pow(x, n)

원문

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

풀이

지수가 0이면 1, 1이면 밑, -1이면 밑의 역수를 반환한다.
그 외의 경우, 지수가 짝수일 때와 홀수일 때로 나누어 함수를 재귀호출한다.

코드

Python

class Solution:
    def myPow(self, x: float, n: int) -> float:
        @cache
        def calc(a, p):
            if p == 0: return 1
            if p == 1: return a
            if p == -1: return 1/a

            if p % 2:
                return a * calc(a, p // 2) * calc(a, p // 2)
            return calc(a, p // 2) * calc(a, p // 2)


        return calc(x, n)

Java

class Solution {
    public double myPow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            return myPow(1/x, Math.abs(n));
        }

        if (n % 2 == 1) {
            return x * myPow(x * x, n / 2);
        }
        return myPow(x * x, n / 2);
    }
}