# O (logn) solution in Java

• /* This is a simple solution based on divide and conquer */

`````` public class Solution {
public double pow(double x, int m) {
double temp=x;
if(m==0)
return 1;
temp=pow(x,m/2);
if(m%2==0)
return temp*temp;
else
{
if(m > 0)
return x*temp*temp;
else
return (temp*temp)/x;
}

}``````

• This post is deleted!

• This post is deleted!

• I consider your solution in python,but leetcode system send me an error "Runtime Error",and then I found "maximum recursion depth exceeded" in my own test.Have you encounted the problem like I show above?If so,how do you solve this problem?

• This post is deleted!

• An O(lgn) iteration solution in similar thought. e.g. x^7=x^(1+2+4)=(x^1)(x^2)(x^4), and x^2=(x^1)(x^1), x^4=(x^2)(x^2).

``````public double pow(double x, int n) {
double result = 1;
int absn = n < 0? n*-1: n;
int curBit = 0;
double curResult = x;
for (int i=0; i<31; i++) {
if ((absn & (1 << i)) > 0) {
for (; curBit<i; curBit++) {
curResult *= curResult;
}
result *= curResult;
}
}
return n < 0? 1 / result: result;
}``````

• Hey, buddy. When we using integer size, sizeof(int)*8 well be better.

• Your algorithm is O(lgn) time complexity and runtime is 16ms

Yours is faster that @ranlei whos code need 40ms.

• Here is my java solution.

``````    public double pow(double x, int n) {
if (n < 0) {
n = -n;
x = 1 / x;
}
double result = 1;
for (double f = x; n > 0; n = n >> 1) {
if (n % 2 == 1) {
result *= f;
}
f = f * f;
}
return result;
}``````

• Beautiful.simply beautiful.

• There maybe overflow error when do n = -n;

• Very concise

• In python, -1/2 is -1 instead of 0, which is different from java. So your python code will never stop recursion if n<0. Knowing this, it's easy to fix.

• when n == -2147483648

• Yep. came up with this idea and got the overflow result when n = Integer.MIN_VALUE....

• How to fix the overflow problem when n = Integer.MIN_VALUE

• @serenewang
We have to handle that special case:

if (n == Integer.MIN_VALUE) {
return (1 / x) * myPow(x, n+1);
}

• I am confused why this is logn. x is multiplied by n times eventually, you just happen to do it by 1 time at a time by dividing it.

• @kmladam lets take the example 3^8. This solution solves it as 3^8 = (3^4)(3^4) = (3^2)(3^2)(3^2)(3^2) = (3)(3)(3)(3)(3)(3)(3)*(3) so how is this logn??

• @kmladam I agree, this seems linear. If you used dynamic programming then it would be log(n) ~ but I could be wrong!

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