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)
1#include <stdio.h>
2
3double myPow(double x, int n) {
4 long long N = n;
5 if (N < 0) {
6 x = 1 / x;
7 N = -N;
8 }
9 double result = 1;
10 while (N) {
11 if (N % 2 == 1) {
12 result *= x;
13 }
14 x *= x;
15 N /= 2;
16 }
17 return result;
18}
19
20int main() {
21 printf("%f\n", myPow(2.00000, 10));
22 printf("%f\n", myPow(2.10000, 3));
23 printf("%f\n", myPow(2.00000, -2));
24 return 0;
25}The C solution iteratively calculates the power using a loop. We adjust for negative exponents by taking the reciprocal of x and converting n to positive. This solution uses long long to handle large powers and iteratively squares the base, multiplying it to the result if the current power is odd.
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
1using System;
public class Solution {
public double MyPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
return MyPowUtil(x, N);
}
private double MyPowUtil(double x, 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;
}
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MyPow(2.00000, 10));
Console.WriteLine(sol.MyPow(2.10000, 3));
Console.WriteLine(sol.MyPow(2.00000, -2));
}
}The recursive C# solution adopts a divide and conquer strategy via a private method to calculate the power. The power is divided recursively, with checks for even or odd powers to complete the computation efficiently.