This post is completed by 1 user

  • 1
Add to List
Beginner

227. Algorithm to calculate power(k,n).

Objective:  Given two numbers ‘k’ and ‘n’. Write an algorithm to calculate kn.
Example:

k = 4, n = 5
kn= 45 = 1024

k = 2, n = 3
kn= 23 = 8

Approach:

Method 1: Brute Force

Use for loop to iterate from 1 to n and do k*k for each iteration.

Time Complexity: O(n)

Output:

4 power 5 :  Result: 1024.0

Method 2: Only if ‘k’ and ‘n’ are positive.

  • Use recursion.
  • Divide the problem into sub-problems with size n/2 and solve it recursively.
  • Handle the case if n is odd. Multiply the final result with k.

Time Complexity: O(logn)

Example:

24= 22* 22= 4*4 = 16.
So instead of doing it 2*2*2*2, we have divided into two parts = 22* 22 

Output:

4 power 5 :  Result: 1024.0

Method 3: Handle the case if n is negative

  • Same as Method 2 above.
  • Instead of multiplying with k, divide with k.
  • See the code for more understanding.

Time Complexity: O(logn)

Output:

4 power -2 :  Result: 0.0625