Pow(x, n)
MediumThe problem
Return x raised to the power n (x multiplied by itself n times). n can be negative, in which case the answer is 1 divided by x^|n|.
- Example 1Input: x = 2.0, n = 10Output: 1024.0
- Example 2Input: x = 2.1, n = 3Output: 9.261
2.1 × 2.1 × 2.1. Tiny rounding differences at the end are fine.
- Example 3Input: x = 2.0, n = -2Output: 0.25
1 / (2 × 2).
Limits
- -100 < x < 100
- -2,147,483,648 ≤ n ≤ 2,147,483,647
- The result fits in a normal float64
- Do not loop n times; n can be huge
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
x^n = (x^(n/2))². How many multiplications does that save? Handle negative n.
The idea
Fast exponentiation: recurse on n/2, square it, multiply by x if n is odd; for negative n invert x.
Target: O(log n) time
Go function shape
func myPow(x float64, n int) float64Reference solution
Tested with go test. Try it yourself first, then compare.
// MyPow: fast exponentiation. x^n = (x^(n/2))^2, times x when n is odd. O(log n) multiplications.
func MyPow(x float64, n int) float64 {
if n < 0 {
return 1 / MyPow(x, -n)
}
if n == 0 {
return 1
}
half := MyPow(x, n/2)
if n%2 == 0 {
return half * half
}
return half * half * x
}