# Pow(x, n) why stack overflow?

• Hi everyone, I got a problem when I dealt with the question Pow(x, n).

This code will get stack overflowed when input ( 1, -2147483648), but (1, -2147483647) is OK.

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

However, the follow code works fine when input ( 1, -2147483648)

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

I think the first solution is just one more time of recursion than the second, and total number of recursion times is 32, why stack overflows?

• Because if n = -2147483648, -n = -2147483648 too when INT_MIN == -2147483648,
You can read this wiki Two's_complement to find out what happen:)

• Because INT_MAX is 2147483647 , when n is -2147483648 , -n is also -2147483648.

So your first code will recurse indefinitely then cause stack overflows.

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