5 different choices when talk with interviewers


  • 138
    M

    After reading some good sharing solutions, I'd like to show them together. You can see different ideas in the code.

    1. nest myPow

    double myPow(double x, int n) {
        if(n<0) return 1/x * myPow(1/x, -(n+1));
        if(n==0) return 1;
        if(n==2) return x*x;
        if(n%2==0) return myPow( myPow(x, n/2), 2);
        else return x*myPow( myPow(x, n/2), 2);
    }
    
    1. double myPow

    double myPow(double x, int n) { 
        if(n==0) return 1;
        double t = myPow(x,n/2);
        if(n%2) return n<0 ? 1/x*t*t : x*t*t;
        else return t*t;
    }
    
    1. double x

    double myPow(double x, int n) { 
        if(n==0) return 1;
        if(n<0){
            n = -n;
            x = 1/x;
        }
        return n%2==0 ? myPow(x*x, n/2) : x*myPow(x*x, n/2);
    }
    
    1. iterative one

    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&1) ans *= x;
            x *= x;
            n >>= 1;
        }
        return ans;
    }
    
    1. bit operation

    see this solution

    If you have other ideas, please leave it below. Thanks.


  • 18
    D

    Need to add more corner cases for iterative solution

    public class Solution {
        public double myPow(double x, int n) {
            if (n == 0) return 1;
            if (x == 1) return 1;
            if (x == -1) {
                if (n % 2 == 0) return 1;
                else return -1;
            }
            if (n == Integer.MIN_VALUE) return 0;
            if (n < 0) {
                n = -n;
                x = 1/x;
            }
            double ret = 1.0;
            while (n > 0) {
                if ((n & 1) != 0) 
                    ret *= x;
                x = x * x;
                n = n >> 1;
            }
            return ret;
        }
    }

  • 0
    J

    I think your code has more if statements and you can simplify it.


  • 3
    H

    Add code when x is 0 or 1. And pay attention to Math.abs(x-0.0)<0.0000001.

    public double myPow(double x, int n) {
        if(n == 0) return 1;
        if(Math.abs(x-0.0)<0.0000001) return 0.0;
        if(Math.abs(x-1.0)<0.0000001) return 1.0;
        
        if(n < 0) x = 1.0/x;
        return Power(x, Math.abs(n));
    }
    
    double Power(double x, int n){
        if(n == 0) return 1;
        if(n == 1) return x;
    
        return ((n&0x1) == 1) ? x*Power(x*x, n/2) : Power(x*x, n/2); 
    }

  • 0
    J
    This post is deleted!

  • -1
    J

    the second solution should be changed like this:

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

  • 2

    redundant solution, not pretty and clean enough


  • 0
    C

    Thank you for adding these corner cases. Seems it is only one could pass OJ now


  • 1
    V

    @daniexia I think your code fails for the case when 0<x<1 and n is Integer.MIN_VALUE.


  • 0
    D
    class Solution {
    public:
        double myPow(double x, long int n) {
            if (n == 0) return 1.0;
            if (n < 0) {
                // For negative exponent, just take inverse.
                return 1.0/myPow(x, -n);
            }
            if (n % 2) {
                return x * myPow(x, n - 1);
            } else {
                double y = myPow(x, n/2);
                return y * y;
            }
        }
    };
    

  • 1
    D

    Another iterative one like 4, may not be the fastest. The idea is to multiply x by n times, but with some speed up giving you an average O(log n) runtime.

    class Solution {
       public:
        double myPow(double x, int n) {
            if (!n) return 1.0;
            if (n < 0) {
                n = -(++n);
                x = 1 / x;
            } else
                n--;
            double result = x;
            while (n) {
                double y = x;
                for (int i = 1; i > 0 && i <= n; i *= 2) {
                    result *= y;
                    y *= y;
                    n -= i;
                }
            }
            return result;
        }
    };
    

  • 1
    J

    @mingjun In my view the first case's time complexity would be O(n) if n < 0. The 3rd and 4th case will not work when n = Integer.MIN_VALUE. Please correct me if I am wrong.


  • 0
    Y

    @daniexia
    Thanks for sharing your solution. However, I think it is inappropriate to compare a double variable with another double due to the precision. For example, in the second line, if (x == 1) return 1; should be replace by if (epsilon > 1-x || epsilon > x - 1) return 1;


  • 0

    Can someone explain why the 3rd solution failed when n = -2147483648? Thanks!


  • 1
    Y

    @shu.zhang It overflows at n = -n because 32-bit Integer ranges from -2147483648 to 2147483647


  • 2
    A

    @shu.zhang As pointed earlier, it suffers from overflow.

    You can convert n to -2147483646 before flipping the sign. (Convert it to -2147483647 will give you incorrect result if the base number is negative.)


  • 0
    J

    @daniexia But this code cannot compile.


  • 0

    if n is negative, first take a multiplication, and then make n-- , lastly n=-n

    public class Solution {
        public double myPow(double x, int n) {
            if (n==0)return 1.0;
            double t = 1.0;
            if (n<0){
                x = 1.0/x;
                n = -(n+1);
                t *= x;
            }
            while (n>=1){
                if ((n&1)==1)
                    t *= x;
                x *= x;
                n = n>>1;
            }
            return t;
        }
    }
    

  • 1
    Q

    @mingjun n < 0 then n = -n will not work. when n = 0x80000000 -2147483648 -n will still get negative, tried?


  • 0

    same idea as the no.3.

        public double myPow(double x, int n) {
            if(n >= 0){
                return helper(x, n);
            }
            else{
                return 1/helper(x, -n);
            }
        }
        
        private double helper(double x, int n){
            if(n == 0) return 1;
            double res = helper(x , n/2);
            res *= res;
            if(n % 2 != 0) res *= x;
            return res;
        }
    

Log in to reply
 

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