Why this code can be accepted if n=INT_MIN?


  • 0
    L

    if a=-2147483648(INT_MIN), -a should be 2147483648,bigger than 2147483647(INT_MAX),
    and in vs2013,the result would still be -2147483648(INT_MIN).

    class Solution {

    public:

    double myPow(double x, int n) {
    	if (n < 0) return 1.0 / power(x, -n);   //this line
    	else return power(x, n);
    }
    

    private:

    double power(double x, int n) {
    	if (n == 0) return 1;
    	double v = power(x, n / 2);
    	if (n % 2 == 0) return v * v;
    	else return v * v * x;
    }
    

    };


  • 0
    Z

    I guess your confusion is about why INT_MIN would fail when integrating this two functions together, like this:

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

    This will fail in the situation 'n == INT_MIN' because -n will always be -2147483648, which would always smaller than 0, the code will keep hanging in the control flow of "if(n < 0 )" and eventually generate run time error.

    But when we split them into two functions, this wouldn't be an issue anymore, since we only check n with 0 once in myPow()


  • 0
    L

    oh,thank you for your reply.but this code is accepted.....my question is that if a=-2147483648(INT_MIN), -a should be 2147483648,bigger than 2147483647(INT_MAX),and in vs2013,the result would still be -2147483648(INT_MIN).


  • 0
    Z

    Yeah...it should works well, i.e: think about such case ---- x = 2, n = INT_MIN, when we call myPow() the result will be 1.0 / power(2, INT_MIN / 2), and the value of power(2, INT_MIN/2) will be something close to inf, so the result will return 0, which is what we expected


  • 0
    L

    good job ! thank you


  • 1
    L

    Boundary Conditions:

    if(x==0 && n==0) result=1;

    if((n<=INT_MIN || n>=INT_MAX) && (x>1 || x<-1)) result=0;

    if(x==1 && n==INT_MIN) result=1;

    if(n>=INT_MAX && (x==1 || x==-1)) result=x;

    if(n<=INT_MIN && (x==1 || x==-1)) result=-x;

       class Solution {
        public:
            double myPow(double x, int n)
            {
                if(x==0 && n==0) return 1;    
                if((n<=INT_MIN || n>=INT_MAX) && (x>1 || x<-1)) return 0;
                if(x==1 && n==INT_MIN) return 1;   // specific patcher   
                if(n>=INT_MAX && (x==1 || x==-1)) return x;
                if(n<=INT_MIN && (x==1 || x==-1)) return -x;
            if(n < 0)
            {
                n = -n;
                x = 1.0/x;
            }
            double res = 1.0;
            for(; n > 0; n >>= 1)
            {
                if((n & 0x1) == 1)  res *= x;
                x *= x;
            }
            return res;
            }
        };
    

  • 0
    L

    perfect !!! thanks


  • 0
    K

    @legege007

    nice job!
    But I think there is a small mistake

     if((n<=INT_MIN || n>=INT_MAX) && (x>1 || x<-1)) return 0;
    

    if n==INT_MAX and (x>1 || x<-1) it should not return 0, it should return a very big value.
    Isn't it?? Or my misunderstanding?


Log in to reply
 

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