**Objective**: Given two numbers ‘k’ and ‘n’. Write an algorithm to calculate k^{n}.

**Example**:

k = 4, n = 5 k^{n}= 4^{5}= 1024 k = 2, n = 3 k^{n}= 2^{3}= 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.

Learn more about bidirectional Unicode characters

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)); | |

} | |

} |

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

2^{4}= 2^{2}* 2^{2}= 4*4 = 16. So instead of doing it 2*2*2*2, we have divided into two parts = 2^{2}* 2^{2}

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

Learn more about bidirectional 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.

Learn more about bidirectional 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)); | |

} | |

} |

**Output**:

4 power -2 : Result: 0.0625