# 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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class KPowerN_Naive { public static double kPowerN(int k, int n){ double result = 1; for (int i = 0; i

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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 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`

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