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.
double myPow(double x, int n) {
if (n == 0) return 1;
if (n < 0) {
x = 1 / x;
n = -n;
}
double res = 1;
while (n) {
if (n & 1) res *= x;
x *= x;
n >>= 1;
}
return res;
}Follow-up:
How would you optimize the solution for very large inputs?
