This post is completed by 1 user
|
Add to List |
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