Similar Idea with Binary


  • 3
    R
    public double myPow(double x, int n) {
            if(n == 0) return 1;
            if(n < 0) {
                n = -n;
                x = 1 / x;
            }
            double ans = 1;
            while(n > 0){
                if((n % 2) != 0) {
                    ans = ans * x;
                }
                x = x * x;
                n = n / 2;
            }
            return ans;
        }

  • 3

    This, like many other similar solutions, break terribly when n is Integer.MIN_VALUE. Fortunately, there seems to be only one test case for that and it's (-1, -2147483648), for which this code gives the correct answer 1. Other tests would overflow and give either infinity or zero, but this code would still return 1 (because the loop never executes, as -n < 0).


  • 0

    Thanks, the case x=2.00000, n=-2147483648 has just been added (thanks, 1337c0d3r).


  • 0
    S

    the first operate on x is very inspiring. If we want to concern the overflow when n = -n, we can do it by negative:

    public double myPow(double x, int n) {
        if(n == 0) return 1.0;
        if(x == 0) return 0.0;
        if(n < 0){
            x = 1.0 / x;
        }else{
            n = -n;
        }
        double rst = 1.0;
        while(n < 0){
            if(n % 2 != 0){
                rst *= x;
            }
            x = x * x;
            n = n / 2;
        }
        return rst;
    }
    

    it passed


Log in to reply
 

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