# 5 different choices when talk with interviewers

• After reading some good sharing solutions, I'd like to show them together. You can see different ideas in the code.

1. nest myPow

``````double myPow(double x, int n) {
if(n<0) return 1/x * myPow(1/x, -(n+1));
if(n==0) return 1;
if(n==2) return x*x;
if(n%2==0) return myPow( myPow(x, n/2), 2);
else return x*myPow( myPow(x, n/2), 2);
}
``````
1. double myPow

``````double myPow(double x, int n) {
if(n==0) return 1;
double t = myPow(x,n/2);
if(n%2) return n<0 ? 1/x*t*t : x*t*t;
else return t*t;
}
``````
1. double x

``````double myPow(double x, int n) {
if(n==0) return 1;
if(n<0){
n = -n;
x = 1/x;
}
return n%2==0 ? myPow(x*x, n/2) : x*myPow(x*x, n/2);
}
``````
1. iterative one

``````double myPow(double x, int n) {
if(n==0) return 1;
if(n<0) {
n = -n;
x = 1/x;
}
double ans = 1;
while(n>0){
if(n&1) ans *= x;
x *= x;
n >>= 1;
}
return ans;
}
``````
1. bit operation

see this solution

If you have other ideas, please leave it below. Thanks.

• Need to add more corner cases for iterative solution

``````public class Solution {
public double myPow(double x, int n) {
if (n == 0) return 1;
if (x == 1) return 1;
if (x == -1) {
if (n % 2 == 0) return 1;
else return -1;
}
if (n == Integer.MIN_VALUE) return 0;
if (n < 0) {
n = -n;
x = 1/x;
}
double ret = 1.0;
while (n > 0) {
if ((n & 1) != 0)
ret *= x;
x = x * x;
n = n >> 1;
}
return ret;
}
}``````

• I think your code has more if statements and you can simplify it.

• Add code when x is 0 or 1. And pay attention to Math.abs(x-0.0)<0.0000001.

``````public double myPow(double x, int n) {
if(n == 0) return 1;
if(Math.abs(x-0.0)<0.0000001) return 0.0;
if(Math.abs(x-1.0)<0.0000001) return 1.0;

if(n < 0) x = 1.0/x;
return Power(x, Math.abs(n));
}

double Power(double x, int n){
if(n == 0) return 1;
if(n == 1) return x;

return ((n&0x1) == 1) ? x*Power(x*x, n/2) : Power(x*x, n/2);
}``````

• This post is deleted!

• the second solution should be changed like this:

`````` public class Solution {
public double myPow(double x, int n) {
if(n==0) return 1;
if(n < 0) {
n = -(n + 1);
return 1 / (x * myPow(x, n));
}
double t = myPow(x,n/2);
if(n%2 == 1) return x*t*t;
else return t*t;
}
}``````

• redundant solution, not pretty and clean enough

• Thank you for adding these corner cases. Seems it is only one could pass OJ now

• @daniexia I think your code fails for the case when 0<x<1 and n is Integer.MIN_VALUE.

• ``````class Solution {
public:
double myPow(double x, long int n) {
if (n == 0) return 1.0;
if (n < 0) {
// For negative exponent, just take inverse.
return 1.0/myPow(x, -n);
}
if (n % 2) {
return x * myPow(x, n - 1);
} else {
double y = myPow(x, n/2);
return y * y;
}
}
};
``````

• Another iterative one like 4, may not be the fastest. The idea is to multiply x by n times, but with some speed up giving you an average O(log n) runtime.

``````class Solution {
public:
double myPow(double x, int n) {
if (!n) return 1.0;
if (n < 0) {
n = -(++n);
x = 1 / x;
} else
n--;
double result = x;
while (n) {
double y = x;
for (int i = 1; i > 0 && i <= n; i *= 2) {
result *= y;
y *= y;
n -= i;
}
}
return result;
}
};
``````

• @mingjun In my view the first case's time complexity would be O(n) if n < 0. The 3rd and 4th case will not work when n = Integer.MIN_VALUE. Please correct me if I am wrong.

• @daniexia
Thanks for sharing your solution. However, I think it is inappropriate to compare a double variable with another double due to the precision. For example, in the second line, `if (x == 1) return 1;` should be replace by `if (epsilon > 1-x || epsilon > x - 1) return 1;`

• Can someone explain why the 3rd solution failed when n = -2147483648? Thanks!

• @shu.zhang It overflows at n = -n because 32-bit Integer ranges from -2147483648 to 2147483647

• @shu.zhang As pointed earlier, it suffers from overflow.

You can convert n to -2147483646 before flipping the sign. (Convert it to -2147483647 will give you incorrect result if the base number is negative.)

• @daniexia But this code cannot compile.

• if n is negative, first take a multiplication, and then make `n--` , lastly `n=-n`

``````public class Solution {
public double myPow(double x, int n) {
if (n==0)return 1.0;
double t = 1.0;
if (n<0){
x = 1.0/x;
n = -(n+1);
t *= x;
}
while (n>=1){
if ((n&1)==1)
t *= x;
x *= x;
n = n>>1;
}
return t;
}
}
``````

• @mingjun n < 0 then n = -n will not work. when n = 0x80000000 -2147483648 -n will still get negative, tried?

• same idea as the no.3.

``````    public double myPow(double x, int n) {
if(n >= 0){
return helper(x, n);
}
else{
return 1/helper(x, -n);
}
}

private double helper(double x, int n){
if(n == 0) return 1;
double res = helper(x , n/2);
res *= res;
if(n % 2 != 0) res *= x;
return res;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.