# Implement pow(x,n) using Java

This is a great example to illustrate how to solve a problem during a technical interview. The first and second solution exceeds the time limit, the third and fourth are accepted.

1. Recursive Method:
In general, we next may think how to do it in O(logn). We have a relation that

`Xn = X2(n/2)*X2(n/2)*X2(n)`

``````package com.algorithm.pow;

//This class has the pow method to calculate pow of X with recursive
public class PowXN {

public static void main(String[] args) {
System.out.println(pow(5.0, 2));
}

public static double pow(double x, int n) {
if (n == 0)
return 1;
if (n == 1)
return x;
int half = n / 2;
int remainder = n % 2;
if (n % 2 == 1 && x < 0 && n < 0)
return -1 / (pow(-x, half) * pow(-x, half) * pow(-x, remainder));
else if (n < 0)
return 1 / (pow(x, -half) * pow(x, -half) * pow(x, -remainder));
else
return (pow(x, half) * pow(x, half) * pow(x, remainder));
}
}``````

2. Accepted Solution:
The accepted solution is also recursive, but does division ﬁrst. Time complexity is O(nlog(n)). The key part of solving this problem is the while loop.

``````package com.algorithm.pow;

/*PowAcceptedSolution class has the method to calculate the pow of X
with with better solution than the recursive way.*/
public class PowAcceptedSolution {

public static void main(String[] args) {
System.out.println(pow(6.0, 3));
}

public static double pow(double x, int n) {
if (n == 0)
return 1;
if (n == 1)
return x;

int pn = n > 0 ? n : -n;// positive n
int pn2 = pn;
double px = x > 0 ? x : -x;// positive x
double result = px;
// handle negative result
if (x < 0 && n % 2 == 1)
result = -result;
// handle negative power
if (n < 0)
result = 1 / result;
int k = 1; // the key part of solving this problem
while (pn / 2 > 0) {
result = result * result;
pn = pn / 2;
k = k * 2;
}
result = result * pow(px, pn2 - k);
return result;
}
}``````

3. Best Solution:
This is the best and easy solution than the above two solutions.

``````package com.algorithm.pow;

public class PowBestSolution {

public static void main(String[] args) {
System.out.println(pow(6.0, 1));
}

public static double power(double x, int n) {
if (n == 0)
return 1;
double v = power(x, n / 2);
if (n % 2 == 0) {
return v * v;
} else {
return v * v * x;
}
}

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

Please let me know if you have any best solutions than the above mentioned.