Implement Pow(x, n)

Problem: Implement Pow(x, n).

Example:

Input: x = 3.00000, n = 3
Output: 27.00000

Input: x = 2.00000, n = -1
Output: 0.5000
Explanation: 2-1 = 1/2 = 0.5

Approach: We can solve it in linear time easily but we need to improve it. We can use divide and conquer here. 

If n is even:

 x ^ n = x ^ (n/2) * x ^ (n/2) 

else:

 x ^ n = x ^ (n/2) * x ^ (n/2) * x

Right. So if you see, we just need to calculate x ^ (n/2) to calculate x ^ n. If we go in this way we can solve it in logarithmic time.

 

Implementation in C#:

    public double MyPow(double x, int n)

    {

        if (n == 0 || x == 1)

        {

            return 1;

        }

        long pow = n;

        if (pow < 0)

        {

            return this.Pow(1/x, -pow);

        }

        return this.Pow(x, pow);

    }

    public double Pow(double x, long n)

    {

        if (n == 1)

        {

            return x;

        }

        double halfPow = this.Pow(x, n/2);

        if (n % 2 == 0)

        {

            return halfPow * halfPow;

        }

        return halfPow * halfPow * x;

    }

Complexity: O(logn)