# 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

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`

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