Given a double, ‘x’, and an integer, ‘n’, write a function to calculate ‘x’ raised to the power ‘n’. For example:

power (2, 5) = 32

power (3, 4) = 81

power (1.5, 3) = 3.375

power (2, -2) = 0.25

- Divide and Conquer

double power(double x, int n) {//TODO: Write - Your - Codereturn x;}

double power_rec(double x, int n) {if (n == 0) return 1;if (n == 1) return x;double temp = power_rec(x, n/2);if (n % 2 == 0) {return temp * temp;} else {return x * temp * temp;}}double power(double x, int n) {bool is_negative = false;if (n < 0) {is_negative = true;n *= -1;}double result = power_rec(x, n);if (is_negative) {return 1 / result;}return result;}bool test_power(double x, int n) {double r1 = power(0.753, n);double r2 = pow(0.753, n);double diff = r1 - r2;if (diff < 0) {diff = diff * -1;}if (diff > 0.00000000001) {cout << "Failed for " << x << ", " << n << endl;return false;}return true;}int main(int argc, char* argv[]) {bool pass = true;for (int n = -5; n <= 5; ++n) {bool temp_pass = test_power(0.753, n);pass &= temp_pass;}pass &= test_power(0, 0);cout << "Power(0, 0) = " << pow(0, 0) << endl;if (pass) {cout << "Passed." << endl;} else {cout << "Failed." << endl;}}

Logarithmic, O(logn).

Logarithmic, O(log n).

The recursive solution has O(logn) memory complexity as it will consume memory on the stack.

A simple algorithm for this problem is to multiply ‘x’ by ‘n’ times. The time complexity of this algorithm would be O(n). We can use the divide and conquer approach to solve this problem more efficiently.

- In the dividing step, we keep dividing n by 2 recursively until we reach the base case i.e. n == 1
- In the combining step, we get the result, ‘r’, of the sub-problem and compute the result of the current problem using the two rules below:
- if n is even, the result is r * r (where r is the result of sub-problem)
- if n is odd, the result is x * r * r (where r is the result of sub-problem)

TRENDING TOPICS