Leetcode: Pow(x, n)

 

This question is asked extremely commonly at Facebook, and sometimes at Microsoft. It is a very simple question:

Implement pow(x,n) which calculates x raised to the power of n (i.e, x^n). The solution is follows:

Using the formula x^(a + b) = x^a * x^b, we can write n as a sum of positive integers, where n = ∑ibi, and we want to get the result as fast as possible. This means that (x^n)^2 = x^2n, and from this we an use the result of x^(2^(i - 1)) to get x^(2i) in one step, indicating that we can do this logarithmically. This may be a bit confusing, but I will try to explain the algorithm to the best of my ability. This is with time complexity O(log n) and space complexity O(1). 

class Solution{

    public double myPow(double x, int n){

        long N = n;

        if(N < 0){

            N = -N;

            x = 1/x;

        }

        double ans = 1;

        double current_product = x;

        for(long i = N; i > 0; i /= 2) {

            if((i % 2) == 1) {

                ans = ans * current_product;

            }

               current_product = current_product * current_product;

        }

        return ans;

    }

}

This solution uses a very short trick of basically taking 2 to the power of certain numbers and them multiplying it and using the remaining odd parity to multiply this. For example let's take 3 to the 23rd power. This means that the current product adds on 23, 11, 5, and 1 or 2^(1 + 2 + 4 + 16) which is a valid additive pair.