# Implement pow(x, n)

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

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/2`

2

``` = 1/4 = 0.25
```

Constraints:

• `-100.0 < x < 100.0`
• `-2`31` <= n <= 2`31`-1`
• `-10`4` <= x`n` <= 10`4

This problem was taken from https://leetcode.com/problems/powx-n/

# Brute force solution:

Straight forward, but we have to consider negative ranges.

```/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {

if(n === 0) {
return 1;
}

var N = n;
var X = x;
var result = 1;

if(n < 0) {
X = 1 / x;
N = -n;
}

for(var i = 0; i < N; i ++) {
result = result * X;
}
return result;
};```

# Approach 2: Fast Power Algorithm Recursive

• divide n so you immediately cut the computation time in half to logarithmic one.

```/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {

function fastPow(x, n) {
if(n < 1) {
return 1;
}
var half = fastPow(x, Math.floor(n / 2));

if(n % 2 == 0) {
return half * half;
}
else {
return half * half * x;
}
}

var X = x;
var N = n;
if(n < 0) {
X = 1 / x;
N = -n;
}
return fastPow(X, N);

};```