pow(x,n)

Posted on Edited on In

problem

\50. Pow(x, n)

Medium

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

1
2
Input: 2.00000, 10
Output: 1024.00000

Example 2:

1
2
Input: 2.10000, 3
Output: 9.26100

Example 3:

1
2
3
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [−231, 231 − 1]

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public double myPow(double x, int n) {

		long N = n;
		if (N < 0) {
			x = 1 / x;
			N = -N;
		}

		double ans = 1;
		double cur = x;//2
		for (long i = N; i > 0; i /= 2) {
			if (i % 2 == 1)
				ans = ans * cur;
			cur = cur * cur;
		}
		return ans;

	}
//偷懒方法
public double myPow(double x, int n) {
		return Math.pow(x, n);
	}

key

其实先使用了偷懒的方法，调用Math库的pow方法，然后写过一版

1
2
3
for(long i=N;i>0;i--) {
	ans=ans*cur;
}

这个会直接报超时的错误，因为的计算量会非常大，在计算（-1.00000，-2147483648）时候超时了，虽然我们可以通过判断x来避免这一个超时，但是我想到了，可以通过n/2来迅速减少相乘的次数。时间大概是8ms

perfect

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public double findPower(double x,long n){
        if(n == Long.valueOf(1))
            return x;
        if(n % 2 == 0){
            double half_pow = findPower(x,n/2);
            return half_pow * half_pow;
        }else{
            double half_pow = findPower(x,(n-1)/2);
            return half_pow * half_pow * x;
        }
        
    }
    public double myPow(double x, int n) {
            if( n==0 )
                return 1;
         
            long n_long = (long) n;
            if( n > 0 )
                return findPower(x,n);
            
            x = 1 / x;
            long n_long_abs =  (long) Math.abs((long)n);
            if(n_long_abs == 1)
                return x;
            return findPower(x,n_long_abs);
    }
}