# 50 - Pow(x, n)

解法一 - 連乘

這個解法最 naive，不過還是寫一下體驗看看感覺：

class Solution {
public:
    double myPow(double x, int n) {
        double res=1;

        for(int i=0; i<abs(n); i++)
            res *= x;

        if(n < 1) res = 1/res;

        return res;
    }
};

在跑到比較長的 case ，例如 pow(0.00001, 2147483647) 就會 TLE，所以顯然要用更聰明的解法。

解法二 - 二分法

很直覺地，我們可以發現 $x^2n = x^n * x^n$，所以我們可以用

• $x*x = x^2$

• $x^2*x^2 = x^4$

依序組合到 $x^n$。

不過照這樣實作，還是無法通過上面的魔王 case：

class Solution {
public:
    double myPow(double x, int n) {
        if(n == 0) return 1.0;

        if(n<0) {
            x = 1/x;
            n = -n;
        }

        if(n == 1) return x;   

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

上面的寫法看似合理，但我每次還是都呼叫了兩次 - myPow(x, n/2)*myPow(x, n/2)，這樣當然沒有省到ＸＤ

class Solution {
public:
    double helper(double x, int n) {
        if(n == 0) return 1.0;

        double half = helper(x, n/2);

        if(n%2 == 0) 
            return half*half;
        else 
            return x*half*half;
    }

    double myPow(double x, int n) {   
        if(n < 0) {
            x = 1/x;
            n = -n;
        }

        return helper(x, n);
    }
};

這樣子又會掛在 pow(1.00000, -2147483648)。

所以需要先處理一下 n，因為 n=-n 時，會 int overflow。

最後通過的程式碼如下：

class Solution {
public:
    double helper(double x, int n) {
        if(n == 0) return 1.0;

        double half = helper(x, n/2);

        if(n%2 == 0) 
            return half*half;
        else 
            return x*half*half;
    }

    double myPow(double x, int n) {   
        long N = n;

        if(N < 0) {
            x = 1/x;
            N = -N;
        }

        return helper(x, N);
    }
};