public class Solution {
public double myPow(double x, int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return x;
}
boolean isNegative = false;
if (n < 0) {
isNegative = true;
n = -1 * n;
}
int k = n / 2;
int l = n - 2 * k;
double t1 = myPow(x, k);
double t2 = myPow(x, l);
double ans = t1 * t1 * t2;
// overflow
if (ans == 0 && n != 0) {
return 0;
}
if (isNegative) {
return 1 / ans;
} else {
return ans;
}
}
}