Pow(x, n)

Implement pow(x,n), which calculates x_raised to the power_n (x^n).

Example 1:

Input:
 2.00000, 10

Output:
 1024.00000

Example 2:

Input:
 2.10000, 3

Output:
 9.26100

Example 3:

Input:
 2.00000, -2

Output:
 0.25000

Explanation:
 2
-2
 = 1/2
2
 = 1/4 = 0.25

Note:

• -100.0 < x < 100.0

• n is a 32-bit signed integer, within the range [−2^31, 2^31 − 1]

Analysis

有几点需要注意：

1. n是有符号的，因此在循环之前，最好统一转化为正整数，如果n是负数，则x变成 1/x，n = -n 即可

2. 由于n取值范围[−2^31, 2^31 − 1] 因此，最好先用长整型long来存n，再转换符号，否则有可能溢出 (To handle the case where N=Interger.MIN_VALUE we use a long (64-bit) variable)

单纯地循环相乘n次之外，更快的方式是fast power，基本思想就是

n = ∑ [(2^i)]

因此 x^n = x^ {∑ [(2^i)]}

x^[2^(i-1)] * x^[2^(i-1)] -> x^[2^i]

例如

x^17 = x^(2^4) * x^(2^0)

x^9 = x^(2^3) * x^(2^0)

x^5 = x^(2^2) * x^(2^0)

Algorithm:

Solution

Fast Power Iterative - O(logn) time

Note using long N for N = -N to avoid overflow.

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double ans = 1;
        double current_product = x;
        for (long i = N; i > 0; i /= 2) {
            if ((i % 2) == 1) {
                ans = ans * current_product;
            }
            current_product = current_product * current_product;
        }
        return ans;
    }
}

Fast Power Recursive - O(logn) time - (8 ms, faster than 83.96%)

class Solution {

    double myPow(double x, int n){

        if (n == 0) {
            return 1.0;
        } else {  
            double half = myPow(x, n / 2);
            if (n % 2 == 0){
                return half * half;
            } else {
                if (n > 0){
                    return half * half * x;
                } else {
                    return half * half / x;
                }                
            }   
        }
    }
}