Implement pow(x, n), 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: 22 = 1/22 = 1/4 = 0.25

Note:
100.0 < x < 100.0 n is a 32bit signed integer, within the range [−2^31, 2^31 − 1]

Solution
Two branch for computing pow(x, n)
with divide and conquer approach.
When n
is odd, pow(x, n) = x * pow(x, n1)
When n
is even, pow(x, n) = pow(x, n/2) * pow(x, n/2).
Note when x is equal with 1.0, we could do a optimization here.
Another corner case is when n
is 2^31, n
will trigger a integer overflow.
#define EPS 1e20 class Solution { public: double myPow(double x, int n) { if(n == 1) return x; if(n == 0) return 1; if(abs(abs(x)  1) < EPS) { if(x > 0) return x; else return n%2 ? x : x; } if(n == INT_MIN) return 0.0; if(n < 0) return 1.0/(myPow(x, n)); if(n%2) return x * myPow(x, n  1); else { double res = myPow(x, n/2); return res * res; } } };
