# 50. Pow(x,n)

Implement [pow(x, n)](http://www.cplusplus.com/reference/valarray/pow/), which calculates `x` raised to the power `n` (i.e., `xn`)

**Example 1:**

<pre><code><strong>Input: x = 2.00000, n = 10
</strong><strong>Output: 1024.00000
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: x = 2.10000, n = 3
</strong><strong>Output: 9.26100
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: x = 2.00000, n = -2
</strong><strong>Output: 0.25000
</strong><strong>Explanation: 2-2 = 1/22 = 1/4 = 0.25
</strong></code></pre>

**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来做.

<table data-header-hidden><thead><tr><th width="103"></th><th width="115.33333333333331"></th><th></th></tr></thead><tbody><tr><td><code>int</code></td><td>4 bytes</td><td>Stores whole numbers from -2,147,483,648 to 2,147,483,647</td></tr><tr><td><code>long</code></td><td>8 bytes</td><td>Stores whole numbers from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807</td></tr></tbody></table>

```
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;
}
```
