Implement pow(x, n), which calculates x raised to the power n
solution :
To implement the power function, we can use the "fast exponentiation" or "exponentiation by squaring" method. This method allows us to compute the power in logarithmic time complexity.
The basic idea is:
x^n = (x^{n/2}) (x^{n/2}) if n is even
public double Pow(double x, int n) {
if (n == 0) return 1.0;
if (n < 0) {
x = 1 / x;
n = -n;
}
return FastPow(x, n);
}
private double FastPow(double x, int n) {
if (n == 0) return 1.0;
double half = FastPow(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
This solution efficiently calculates in O(log n) time complexity.