1.

Write a program in Java to calculate pow(x,n) using recursion. The expected time complexity is O(log2N) where N is the power. You cannot use any extra space apart from the recursion call stack space.

Answer»

We have seen how we can calculate the pow(x,n) in linear time. We can optimize our approach by changing the recurrence relation. Let us understand this with the help of an example shown below:

So, we can see that if the power is even, we can divide the power by 2 and can multiply x to the power n/2 by itself to get our answer. What if the power of the number is odd? 

In that case, we multiply the number x once to the term x to the power n/2 multiplied by itself. Here, n/2 will be the floor value of (n/2). You can verify this for any pair of x and n.

So, doing this will reduce the time complexity from O(N) to O(log2N). This happens because of the change in recurrence relation and the recursion tree as shown below.

Solving these recurrence relations gives us the respective time complexities. So, the code for O(log2N) approach is shown below

Java Code for (x to the power N) in Logarithmic Time Complexity

import java.util.*;
class Main {

public static double power(double x, int n) {
if(n == 0) return 1.0;

double xpnby2 = power(x,n/2); //xpnby2 = x power n by 2

if(n % 2 == 0) return xpnby2 * xpnby2; //if power is even

return x * xpnby2 * xpnby2; //if power is odd
}

public static double pow(double x, int n) {
if(n < 0) {
return 1.0 / power(x,-n);
}

return power(x,n);
}
public static void main(String args[]) {
// Your code goes here
Scanner scn = new Scanner(System.in);
double x = scn.nextDouble();
int n = scn.nextInt();

System.out.println(pow(x,n));
}
}

Sample Output:

  • For positive Power
Input:
1.10
3

Output: 1.3676310000000003
  • For negative Power
Input:
1.110
-3

Output:
0.7311913813009502


  • Corner Cases, You Might Miss: The power of a number can be negative too. So, we know that x-n = (1/xn). In this way, we can handle the corner test case of a power being negative.


  • Time Complexity: As already discussed, Time Complexity is O(log2N).


  • Auxiliary Space: The auxiliary space is O(1) as we have not used any extra space.


Discussion

No Comment Found

Related InterviewSolutions