[Leetcode 50] 實作數字次方pow(double x, int y)

兩種方法：

C code solution 1 (Time Exceeded):

double pow(double x, int y){
    double res = 1;
    for(int i=0; i<y; i++){
        res = res * x;
    }
    return res;
}

此種方法時間複雜度為O(y)，多少次方即跑多少次迴圈。

C code solution 2 (recursive):

double pow_new(double x, int y){
    //boundaries
    if(x == 1 || x == 0)
        return x;
    if(y == 0)
        return 1;
        
    //main section
    int pow = 1;
    double res = x;
    //mutiply the power by 2 everytime to speed up
    while(pow*2 <= y){
        res = res * res;
        pow *= 2;
    }
    //if the power is not 2's power, continue to mutiply the rest
    return res * pow_new(x, y-pow);
}

C code solution 2 (iterative):

double pow_new(double x, int y){
    //boundaries
    if(x == 1 || x == 0)
        return x;
    if(y == 0)
        return 1;
        
    //main section
    double res = 1;
    //mutiply the power by 2 everytime to speed up
    while(y > 0){
        int target = y;
        int pow = 1;
        double sub_res = x;
        while(pow*2 <= target){
            sub_res = sub_res * sub_res;
            pow *= 2;
        }
        y = y - pow;
        res *= sub_res;
    }
    
    return res;
}

此種方法每次都將結果平方(2*2=4 → 4*4=8 → 8*8=16…)，若次方非2的冪次方，則做到目前最大的2的冪次方，再乘上剩下的部分，例如 2⁷ 會拆解成 2⁴ * 2² * 2¹。此種方法的時間複雜度為O(log(y))。

C code solution 2 (Dynamic programming):

long pow_dp(long x, int y){
    //boundaries
    if(x == 1 || x == 0)
        return x;
    if(y == 0)
        return 1;
        
    //main section
    long res = x;
    long dp[10000] = {0};
    //mutiply the power by 2 everytime to speed up
    //process the largest power of 2's power of number for the first time
    long pow = 1;
    dp[0] = 1;
    dp[1] = x;
    while(pow*2 <= y){
        res = res * res;
        pow *= 2;
        dp[pow] = res;
    }
    //getting the rest power
    y = y - pow;
    //use dp to finish the rest
    //mutiply all the power of non-2's power of number, eg 2^5, 2^9, and find the largest power of 2's power at the same time
    while(dp[y] == 0){
        long tmp = y & (y-1);
        res *= dp[tmp];
        y = y - tmp;
    }
    //mutiply the largest power of 2's power
    res *= dp[y];
    
    return res;
}

此種方法運用先找出y的最大2的冪次方是多少，隨著尋找的同時也記錄經過的所有x的2的冪次方次方在DP中。最受剩下來的次方發現剛好都可以由剛才DP所記錄下來的數來查找到，把找到的結果再相乘，得到最終結果。

Leetcode 50. Pow(x, n)

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

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/22 = 1/4 = 0.25

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

C code solution:

double myPow(double x, int n){
    //boundaries
    if(x == 1 || x == 0)
        return x;
    if(n == 0)
        return 1;
        
    //main section
    long int y = n;
    bool neg_flag = false;
    //check if the power is negative
    if(y<0){
        y = -1 * y;
        neg_flag = true;
    }
    
    double res = 1;
    //mutiply the power by 2 everytime to speed up
    while(y > 0){
        long int target = y;
        long int pow = 1;
        double sub_res = x;
        while(pow*2 <= target){
            sub_res = sub_res * sub_res;
            pow *= 2;
        }
        y = y - pow;
        res *= sub_res;
    }
    
    //if the power is negative, 1/res
    if(neg_flag)
        res = 1.0 / res;
    
    return res;
}

How others do (very clean!):

double myPow(double x, int n){
    double res = 1;
    while (n) {
        if (n % 2) res = n > 0 ? res * x : res / x;
        x = x * x;
        n /= 2;
    }
    return res;
}