# 50. Pow(x, n)

## problem description

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

**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/22 = 1/4 = 0.25
```

**Note:**

* -100.0 < *x* < 100.0
* *n* is a 32-bit signed integer, within the range \[−231, 231 − 1]

## algorithm thought

求2的100次方，如果直接乘100次，其实没有必要。完全可以求4的50次方，然后16的25次方。这样每次能减少一半的计算量。这里的问题就是还有负数。如果是负数的话，首先将x化为1/x。然后将n转化为正数。最后，一种最特殊的情况就是如果数字是INT\_MIN,最后直接将n-1即可。这样INT\_MIN就会变INT\_MAX

## code

```cpp
class Solution {
public:
    double myPow(double x, int n) {
        if(n==0)
            return 1;
        if(n<0){
            x=1/x;
            if(n==INT_MIN){
                return x*myPow(x,(n-1));
            }
            n=-n;
        }
        return n%2?x*myPow(x*x,n/2):myPow(x*x,n/2);
    } 
};
```

## algorithm analysis

每次将次数降低一半，时间复杂度O(lgn)
