Sponsored
Sponsored
The iterative method with exponentiation by squaring is an efficient way to calculate powers. It reduces the time complexity by squaring the base and halving the power at each step. This method leverages the mathematical property that xn = (x2)n/2 when n is even and xn = x * xn - 1 when n is odd. By iteratively updating the base and reducing the power, this method achieves a logarithmic time complexity.
Time Complexity: O(log n), Space Complexity: O(1)
1class Solution:
2 def myPow(self, x: float, n: int) -> float:
3 if n == 0:
4 return 1
5 N = n
6 if N < 0:
7 x = 1 / x
8 N = -N
9 result = 1
10 while N != 0:
11 if N % 2 != 0:
12 result *= x
13 x *= x
14 N //= 2
15 return result
16
17sol = Solution()
18print(sol.myPow(2.00000, 10))
19print(sol.myPow(2.10000, 3))
20print(sol.myPow(2.00000, -2))The Python solution handles negative powers by adjusting the base and uses integer division to halve the power in each iteration. Python's native floating-point operations simplify handling the precision required for real-number computations.
The recursive divide and conquer method further optimizes power calculation by dividing the problem into smaller subproblems. By recursively dividing the power by 2, this approach minimizes the number of multiplications. If the power is even, it computes (xn/2)2, and if odd, it adjusts with an additional multiplication. This recursive approach can be more intuitive, especially for understanding the problem breakdown.
Time Complexity: O(log n), Space Complexity: O(log n) due to the call stack
1
class Solution {
public:
double myPow(double x, int n) {
long long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
return myPowUtil(x, N);
}
private:
double myPowUtil(double x, long long n) {
if (n == 0) return 1;
double half = myPowUtil(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
};
int main() {
Solution sol;
std::cout << sol.myPow(2.00000, 10) << std::endl;
std::cout << sol.myPow(2.10000, 3) << std::endl;
std::cout << sol.myPow(2.00000, -2) << std::endl;
return 0;
}The C++ recursive solution is similar to the C version, leveraging a private helper method within a class to perform the recursive computation. This method divides the exponent recursively and adjust calculations for odd exponents.