My Straightforward Solution with Explanation


  • 1
    Y

    I use the divide-n-conquer method to solve this. At each step, if n is even, then we simply calculate temp = pow(x, n/2) and return temp * temp. If n is odd, then we need to do x * temp * temp, because the division is rounded to the nearest floor so we will be missing one x.

    I also wrote code to handle the special case where n == Integer.MIN_VALUE. In that case we can't simply covert n to a positive value. We divide it into half and use the partial results to get the final answer.

    It doesn't handle the case where the result of myPow overflows.

    Time complexity is O(log(n)), because each step we are dividing n by half.

    public class Solution {
        public double myPow(double x, int n) {
            // base case
            if (n == 0) {
                return 1;
            }
            // handle negative situation
            if (n < 0) {
                if (n == Integer.MIN_VALUE) {
                    double temp = myPow(x, -(n/2));    // Integer.MIN_VALUE is an even number
                    return 1 / (temp * temp);
                } // else
                return 1 / myPow(x, -n);
            }
            // general situation
            double temp = myPow(x, n/2);
            if (n % 2 == 0) {
                return temp * temp;
            } // else
            return x * temp * temp;
        }
    }
    

Log in to reply
 

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