Analysis:

If we just use the normal way of calculation, when face 1 to the power of 10000, the computation complexity is too high.

Consider this way:

If we want to get 2^10,

2^10 = 2^4 * 2^4 *2^2

2^4 = 2^2*2^2

2^2 = 2*2

Let's see this in a bottom-up way, totally it needs to loop n/2 > 0 times, first we have 2^1=2, then we can have 2^2 = 2*2=4, and again we have 2^4 = 4*4, (key point:) and if n%2==1, we need one more previous value, which is 2^2 here, so we have 2^4*2^4*2^2 = 2^10.

Details see the code below.

Source Code:

class Solution { public: double pow(double x, int n) { // Start typing your C/C++ solution below // DO NOT write int main() function int sign = n>=0?1:-1; double y=1; for (int i=0;i<abs(n);i++){ y=y*x; } if (sign==-1) {return 1/y;} else {return y;} } };

class Solution { public: double pow(double x, int n) { // Start typing your C/C++ solution below // DO NOT write int main() function if (x==0){ if (n==0){return 1;} else {return 0;} } if (n==0){ return 1; } bool pos=true; if (n<0){ pos = false; n=abs(n); } double np=x; double res=1; while (n>0){ if (n%2==1){ res = res * np; } np=np*np; n=n/2; } return pos? res:1/res; } };

Wouldn't n =int_min cause overflow in ur solution?

ReplyDeleteNing Zhu is right

Deleteyou can reference this:

// nonrecursive implementation

// its not the fast one, only runtime beats 29.88% of java submissions on 2/1/2016.

static double power2(double x, int n) {

if (x == 1) {

return 1;

}

if (x == -1) {

return n % 2 == 0 ? 1 : -1;

}

boolean negative = false;

if (n < 0) {

negative = true;

n = -n;

}

double result = 1;

while (n != 0) {

if ((n & 1) == 1) {

result *= x;

}

x *= x;

n >>= 1;

}

return negative ? 1 / result : result;

}

This comment has been removed by the author.

ReplyDelete