Ac solution code


  • 0

    The basic idea is using Divid&Conquer to divide myPow(x, n) to half myPow(x, n), then merge the result. A little trick is how to deal with the boundary of negative n, as the following:

    Solution1. Recursive Solution - O(lgn) runtime; O(lgn) space

    public double myPow(double x, int n) {
    	if (n == 0) return 1;
    	if (n < 0) return 1.0 / ( x * myPow(x, -n - 1));// Integer.MIN_VALUE=-2147483648; Integer.MAX_VALUE=2147483647
    	double half =  myPow(x, n / 2); // Divid
    	return (n % 2 == 1 ? x : 1) * half * half; // Conquer
    }
    

    Solution2. Iterative Solution - O(lgn) runtime; O(lgn) space

    public double myPow(double x, int n) {
        double res = 1.0;
        int m = Math.abs(n);
        Stack<Integer>stack = new Stack<Integer>();
        while (m != 0) {
            stack.push(m);
            m /= 2;
        }
        while (stack.size() != 0) 
            res = (stack.pop() % 2 == 1 ? x : 1) * res * res;
        return (n < 0) ? 1.0 / res : res;
     }

Log in to reply
 

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