Pow(x, n) why stack overflow?


  • 0
    Z

    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?


  • 0
    T

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


  • 0
    W

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

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


Log in to reply
 

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