Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Calculate Power of a Number

Explore how to calculate a number raised to an integer power efficiently by applying a divide and conquer algorithm. Learn to break down the problem recursively, handling even and odd powers to reduce the number of multiplications. Understand the time and space complexities involved to optimize your coding solutions in mathematical problem solving.

We'll cover the following...

Statement

Given a double number, xx, and an integer, nn, implement a function to calculate xx raised to the power nn.

Example:

Given input

Power

power(0, 0)

1.000

power(2, 5)

32.000

power(3, 4)

81.000

power(1.5, 3)

3.375

power(2, -2)

0.250

Sample input

pow(2,5)

Expected output

32

Try it yourself

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
double Power(double x, int n) {
	//TODO: Write - Your - Code
	return x;
}

Solution

A simple algorithm for this problem is to multiply x with itself by n times:

We can reduce the number of multiplications, in a classic divide and conquer approach, exploiting this property of exponents:

  • xn=xn2×xn2x^n=x^{\frac{n}{2}} \times x^{\frac{n}{2}}
...