# Pow(x, n)

Implement [pow(*x*,*n*)](http://www.cplusplus.com/reference/valarray/pow/), 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:**

![](https://1611446478-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M63nDeIUEfibnkE8C6W%2Fsync%2Fcd22f34b40d07b70d9bcfce23b76f3d3e440a15d.png?generation=1588144785569724\&alt=media)

## Solution

### Fast Power Iterative - O(logn) time

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

```java
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%)

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