Description

Pow(x, n)

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

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/2}^2 = 1/4 = 0.25

Note:

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

求x的n次方。

Solution

使用分治法将n次方分解为n/2次方问题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func myPow(x float64, n int) float64 {
    if x == 0 || x == 1 {
        return x
    } else if n == 0 {
        return 1
    } else if n < 0 {
        return myPow(1/x, -n)
    } else if n&1 == 0 {
        return myPow(x*x, n/2)
    } else {
        return x * myPow(x*x, n/2)
    }
}

Similar Problem

• 69. Sqrt(x)