Pow(x, n)
Implement pow(x, n), which calculates x raised to the power of n (i.e., x^n).
Constraints:
- -100.0 < x < 100.0
- -2^31 <= n <= 2^31-1
- -10^4 <= x^n <= 10^4
Examples:
Input: 2.00000, 3
Output: 8.00000
Explanation: 2^3 = 8
Input: 2.10000, 3
Output: 9.26100
Explanation: 2.1^3 = 9.261
Input: 2.00000, -3
Output: 0.12500
Explanation: 2^(-3) = 1/2^3 = 1/8 = 0.125
Solutions
Divide and Conquer
Time: O(log n)Space: O(1)
The idea is to use the divide and conquer approach to calculate x^n. If n is even, we can calculate x^(n/2) and then square the result. If n is odd, we can calculate x^((n-1)/2), square the result, and then multiply by x.
def myPow(x:
float, n:
int) -> float:
if n == 0:
return 1 if n < 0:
x = 1 / x n = -n res = 1 while n:
if n & 1:
res *= x x *= x n >>= 1 return resFollow-up:
How would you optimize the solution for very large inputs?
