1.

Write a Java Program to calculate xn (x to the power n) using Recursion. You can use O(N) time but can’t use any extra space apart from the Recursion Call Stack Space.

Answer»

In a recursive function, we need to find a relation between the smaller problem and the larger problem. Here, we have a clear mathematical relationship between the large problem xn and the problem that is smaller than it i.e. x to the power (n-1). The relation is:

xn = x * xn-1{"detectHand":false}

The relation is: (x to the power n)  = x * x to the power(n-1)

In terms of programming (using functions), we can write this relation as: power(x,n) = x * power(x,n-1)

For example, 2 to the power 5 = 32. This can be calculated as 2 * (2 to the power 4) = 2 * 16 = 32. So, we have found the recurrence relation in the above equation. Now, what will be the base case?

The base case will be the smallest such problem that we can solve. So, the smallest problem is calculating the power of 0 to any number. We know that any number to the power 0 gives the result as 1. So, this will be our base case.

Now, let us write the code for the same.

Java Code to Calculate x to the power n

import java.util.*;
class Main {

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

double xpnm1 = power(x,n-1); //x power n-1 (xpnm1)

return x * xpnm1;
}

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 to the power -n) = [1/(x to the power n)]. In this way, we can handle the corner test case of a power being negative. What if the number is negative? Is our code handling that case? Yes, it does. Why? Try to think about this.


  • Time Complexity: The time complexity of this code is O(N) where N is the power. We see that the time complexity does not depend on X i.e. the number. It only depends on the power of the number.


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


Discussion

No Comment Found

Related InterviewSolutions