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)

Code:

public class KPowerN_Naive {
public static double kPowerN(int k, int n){
double result = 1;
for (int i = 0; i <n ; i++) {
result *= k;
}
return result;
}
public static void main(String[] args) {
int k = 4;
int n = 5;
System.out.println(k + " power " + n + " : Result: " + kPowerN(k,n));
}
}

view raw
KPowerN_Naive.java
hosted with ❤ by GitHub


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

1.     Use recursion.

2.     Divide the problem into sub problems with size n/2 and solve it recursively.

3.     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

Code:

public class KpowerN_OnlyPositive {
public static double kPowerN(int k, int n){
if(n==0)
return 1;
double halfResult = kPowerN(k, n/2);
if(n%2==0){
return halfResult*halfResult;
}else{ //n is odd
return halfResult*halfResult*k;
}
}
public static void main(String[] args) {
int k = 4;
int n = 5;
System.out.println(k + " power " + n + " : Result: " + kPowerN(k,n));
}
}


Method 3: Handle the case if n is negative

1.     Same as Method 2 above.

2.     Instead of multiplying with k, divide with k.

3.     See the code for more understanding.

Time Complexity: O(logn)

Code:

public class KpowerN {
public static double kPowerN(int k, int n){
if(n==0)
return 1;
double halfResult = kPowerN(k, n/2);
if(n%2==0){
return halfResult*halfResult;
}else if(n>0){ //n is odd
return halfResult*halfResult*k;
}else // n<0
return halfResult*halfResult/k;
}
public static void main(String[] args) {
int k = 4;
int n = 2;
System.out.println(k + " power " + n + " : Result: " + kPowerN(k,n));
}
}

view raw
KpowerN.java
hosted with ❤ by GitHub

Output:

4 power -2 :  Result: 0.0625

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.