LeetCode - 50. Pow(x, n) // Java

문제

 

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

 

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

 

Constraints:

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1
• -10^4 <= xn <= 10^4

---

풀이

 

pow(x, n)을 직접 구현하는 문제이다.

 

x를 n번 곱해서 구할 수도 있지만, n의 범위가 MIN_INT ~ MAX_INT이기 때문에 시간 초과가 발생할 것이다.

 

따라서, 분할 정복을 이용하여 거듭 제곱을 구해야 한다!

 

 

x^n은 다음과 같은 경우로 구할 수 있다.

• n이 짝수 : x^(n/2) * x^(n/2)
• n이 홀수 : x^(n/2) * x^(n/2) * x

 

여기서 주의할 점은, n이 음수일 때는 1/(x^n)을 결과로 반환해야 한다는 점이다.

 

따라서, 분할 정복을 통해 쪼갤 때 함수의 인자로 (n/2) * -1를 함수의 인자로 보낸 뒤 마지막에 1 / (값) 을 해주면 된다!

---

코드

class Solution {
    public double myPow(double x, int n) {
        if(n == 0)
            return 1;
        else if(n < 0){
            if((n * -1) % 2 == 0){
                double temp = myPow(x, n/2 * -1);
                return 1 / (temp * temp);
            }
            else{
                double temp = myPow(x, n/2 * -1);
                return 1 / (temp * temp * x);
            }
        }
        else{
            if(n % 2 == 0){
                double temp = myPow(x, n/2);
                return temp * temp;
            }
            else{
                double temp = myPow(x, n/2);
                return temp * temp * x;
            }
        }
    }
}