LeetCode - Algorithms - 50. Pow(x, n)

Problem

50. Pow(x, n)

Java

Accepted

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public double myPow(double x, int n) {
		if (x==0.0d && n==0)
			return Double.POSITIVE_INFINITY;
		if (n>=0) {
			return myPow_recur(x, n);
		}
		else {
			double reciprocal = myPow_recur(x, -n);
			return 1.0/reciprocal;
		}       
    }

	private double myPow_recur(double x, int n) {
		if (n==0) return 1;
		double square = myPow_recur(x,n/2);
		if ( (n & 1) == 1 ) {
			return x*square*square;
		}
		return square*square;
	}
}

Submission Detail

  • 304 / 304 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Pow(x, n).
  • Memory Usage: 36.6 MB, less than 5.88% of Java online submissions for Pow(x, n).

Time Limit Exceeded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public double myPow(double x, int n) {
    	if (x==0.0d && n==0)
    		return Double.POSITIVE_INFINITY;
        double y = 1;
        if (n==0)
        	y=1;
        if (n>0) {
        	for(int i=n;i>0;i--)
        		y*=x;
		}
        if (n<0) {
        	double reciprocal = 1;
        	for(int i=-n;i>0;i--)
				reciprocal*=x;
        	y = 1.0/reciprocal;
		}
        return y;        
    }
}

Submission Detail

  • 299 / 304 test cases passed.
  • Status: Time Limit Exceeded

ref