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

Advertisement