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)
1public class Solution {
2 public double myPow(double x, int n) {
3 long N = n;
4 if (N < 0) {
5 x = 1 / x;
6 N = -N;
7 }
8 double result = 1;
9 while (N != 0) {
10 if (N % 2 != 0) {
11 result *= x;
12 }
13 x *= x;
14 N /= 2;
15 }
16 return result;
17 }
18
19 public static void main(String[] args) {
20 Solution sol = new Solution();
21 System.out.println(sol.myPow(2.00000, 10));
22 System.out.println(sol.myPow(2.10000, 3));
23 System.out.println(sol.myPow(2.00000, -2));
24 }
25}In Java, the solution manages powers similarly to C and C++. It uses the long type to handle potential overflow issues with negative powers by converting the integer n to a positive equivalent. The main loop efficiently computes the power using the squaring method.
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
In this Python solution, a nested helper function performs the recursive calculation. It divides the power by 2 recursively and uses the result to obtain xn. This structure leverages Python's concise function definitions.