# 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 = ∑ [(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;
}
}
}
}
}
``````