leetcode Question 74: Pow(x,n)

Pow(x,n)

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;

}
};


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

1. Ning Zhu is right
you 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;
}

2. This comment has been removed by the author.