[leetcode] 50. Pow(x, n)

x^n 결과를 구하는 문제입니다.

leetcode.com/problems/powx-n/

Pow(x, n) - LeetCode

이 문제는 x를 n번 루프를 돌려서 풀면..

타임아웃이 나버립니다.

 

2^10이라고 10번 2를 곱해줄것이 아니라

2^10 = 2^4 * 2^4 * 2^2 

2^4  = 2^2 * 2^2

2^2

해서 총 세번의 연산으로 최종 값을 구할 수 있습니다.

 

아래 코드는.. i를 n부터 시작해서 i를 반씩 나눠주며 계산합니다.

i % 2 == 1는 어떤 경우일까요?

2^9 = 2^4 * 2^4 * 2*2^1

위의 빨간색 부분과 같이 n이 홀수라서 이후 연산에 무관해진 시점이라고 생각하면 됩니다.

그래서 이 때는 최종 결과에 누적곱을 해주고,

쭉 계산하다가 마지막 i는 1이 될테니... n이 짝수였을 때 누적된 곱들을 한번에 뽝 .. 결과에 곱해서 결과를 내는 방식입니다.

 

추가로, 

n값이 0보다 작은 경우 절대값을 취해주는데, 

그냥 n * -1 해줄 경우 숫자가 크면 잘 안될 수 있습니다.

그래서 n을 잠시 long형 temp변수에 넣었다가 쓰거나 하는 방식으로 처리해야 합니다.

class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        double curr = x;
        for(long i = Math.abs((long)n); i > 0; i=i/2) {
            if(i % 2 == 1) {
                res = res * curr;
            }
            curr = curr * curr;
        }
        return n < 0 ? 1/res : res;
    }
}