문제

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

제한사항

• -100.0 < x < 100.0
• -$2^{31}$ $\leq$ n $\leq$ $2^{31}$-1
• -$10^4$ $\leq$ $x^n$ $\leq$ $10^4$

접근

단순한 Math.pow 인터페이스를 구하는 문제에요. 여기서 관건은 n이 매우 큰 값을 가질 경우 연산을 최소화하는 방식을 찾는 것이에요.

이분탐색으로 재귀적으로 접근하면 되요. x * x는 곱하는 수치의 2배가 되요. $2^{10} * 2^{10} = 2^{20}$을 생각하시면 되요.

그렇게 연산을 최소화하는 방식으로 접근하시면 답을 도출하실 수 있어요. n의 수치가 2로 나눠지지 않을 땐 x를 한번 더 곱하고 (n-1)/2의 수치로 재귀 접근하시면 되요.

답안

class Solution {
    
    public double myPow(double x, int n) {

        return (0 <= n) ? pow(x, n) : 1 / pow(x, -n);
    }

    public double pow(double x, int n){
        if(n == 1){
            return x;
        } else if(n == 0){
            return 1.0f;
        }
        if(n % 2 == 0){
            return pow(x * x, n >>> 1);
        } 
        return x * pow(x * x, (n - 1) >>> 1);
    }
}