Power of a Number

editor-page-cover

Problem Statement

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


Hint

  • Divide and Conquer

Try it yourself

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

Solution

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;
  }
}

Solution Explanation

Runtime Complexity

Logarithmic, O(logn).

Memory Complexity

Logarithmic, O(log n).

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


Solution Breakdown

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)