# Iterative Log(N) solution with Clear Explanation

• I couldn't find a clear explanation for an interative Log(n) solution so here's mine. The basic idea is to decompose the exponent into powers of 2, so that you can keep dividing the problem in half. For example, lets say

N = 9 = 2^3 + 2^0 = 1001 in binary. Then:

x^9 = x^(2^3) * x^(2^0)

We can see that every time we encounter a 1 in the binary representation of N, we need to multiply the answer with x^(2^i) where i is the ith bit of the exponent. Thus, we can keep a running total of repeatedly squaring x - (x, x^2, x^4, x^8, etc) and multiply it by the answer when we see a 1.

To handle the case where N=INTEGER_MIN we use a long (64-bit) variable. Below is solution:

public class Solution {
public double MyPow(double x, int n) {
double ans = 1;
long absN = Math.Abs((long)n);
while(absN > 0) {
if((absN&1)==1) ans *= x;
absN >>= 1;
x *= x;
}
return n < 0 ?  1/ans : ans;
}
}

• this solution was perfect!

• Thanks for sharing the solution. Can you help explain why the complexity is O(log n) versus O(1) since we are looping through the bits of N which is fixed in number?

• Yes, since you're dividing N by 2 every iteration that's why it is O(Log N). However, since N is a fixed number of bits (32) you could view it as O(1) where the maximum number iterations is 32. Hope this helps.

• Thanks for sharing your solution. Amazing!!!

• This post is deleted!

• this solution is beautiful.

i have a question.

how to this solution solve stackoverflowexception.

long temp = (long) x;
if (n == 0) {
return 1.0;
}

if (n < 0) {
return 1.0 / (temp * (long) myPow(temp, n - 1));
}

return (temp * (long) myPow(temp, n - 1));

this is mine.

but it has stackoverflowexception

• This post is deleted!

• 1001

Your idea is good but you don't have to think in this way.
This iterative version just re-write the idea of its recursive version from https://discuss.leetcode.com/topic/21837/5-different-choices-when-talk-with-interviewers:
double myPow(double x, int n) {
if(n==0) return 1;
if(n<0){
n = -n;
x = 1/x;
}
return n%2==0 ? myPow(xx, n/2) : xmyPow(x*x, n/2);
}

• @renwoxing Well, I think the iterative version isn't so obviously derived from the recursive version (at least not to me) that it deserves its own post. If the interviewer asks for iterative version and one couldn't come up with it that wouldn't look too good :P

• This post is deleted!

• Somehow literal code snippet failed with "Unable to find method Abs(long)". It should be

long absN = Math.abs((long)n)

Minor correction. Thanks for the solution above all.

• diao de yi bi

• @jonathan82 good one

• @jonathan82 Amazing! Thx

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