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

• -2^31 <= n <= 2^31-1

• n is an integer.

• -10^4 <= x^n <= 10^4

My Solutions:

方法1: iterate n times, Time: O(N), 如果n非常大，会导致超时。

方法2:用二分法，比如2^4，其实就是4^2,这样Time: O(logN)。但是如果用以下recursive写会导致stack overflow。

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

    if (n % 2 == 1) return x * myPow(x, n - 1); // 比如x的3次方，可以转化成x*myPow(x,2)
    else {
        double curr = myPow(x, n / 2); //比如n的4次方，可以转化成mypow(n, 2)，在下一步再把这个结果^2.
        return curr * curr;               
    }
}

方法3: 优化一下方法2。如果n是奇数，先用结果*x，让n-1变成偶数。然后x=x*x, n=n/2

注意input的n是个int，所以有可能是负数(-2147483648)，必须要把ta转换成一个long来做.

int	4 bytes	Stores whole numbers from -2,147,483,648 to 2,147,483,647
long	8 bytes	Stores whole numbers from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807

public double myPow(double x, int N) {
    long n = Long.valueOf(N); // 注意这里
    if (x == 1) return 1;
    if (n == 0) return (double) 1;
    if (n == 1) return x;
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    
    double ans = 1;
    while (n > 0) {
        if (n % 2 == 1) ans *= x;
        x *= x;
        n /= 2;
    }

    return ans;
}