Pow(x, n)

Question: Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

You may view the full question here.

Approach 0: Let’s first begin with a method that helps you do the “initial prep”. To be more specific, we have special cases such as dealing with negative powers or power=0, or edge cases such as dealing with base number=1 or 0. If we can handles all these cases in one method, right at the beginning and have the actual computation done in a secondary method which specifically deals only with positive powers — we can have the problem significantly simplified.

Now the primary method that handles initial data clean looks like this —

public double myPow(double x, int n) {
        double nD = n;
        if(n==0 || x==1){
            return 1;
        } else if(n<0) {
            x = 1/x;
            nD=(-1)*(double)n;
        }
        return secondaryMethod(x,nD);
    }

Approach 1: An iterative version of the power computation looks like this —

//Approach 1:
//Runtime: 1156ms //that's right!!!
//Memory usage: 34.4MB
class Solution {
    public double myPow(double x, int n) {
        double nD = n;
        if(n==0 || x==1){
            return 1;
        } else if(n<0) {
            x = 1/x;
            nD=(-1)*(double)n;
        }
        return pow(x,nD);
    }
    
    private double pow(double x, double n){
        double p = 1;
        double res = x;
        while((p*2)<=n){
            res*=res;
            p*=2;
            if(res==0){
                return 0;
            }
        }
        for(int i = 0; i<(n-p); i++){
            res*=x;
        }
        return res;
    }
}

Now, consider the example power number to be 15. The iteration looks like —

1*2 = 2

2*2 = 4

4*2 = 8

̶8̶*̶2̶ ̶=̶ ̶1̶6̶ (16>15)

So, we stop at 8, and continue the computation by multiplying the base value 7 (15–8) times!!!

Approach 2: The solution to this problem will be to start with the actual power, and break it down into smaller units. We have a simple implementation using recursion here —

//Approach 2:
//Runtime: 1ms 
//Memory usage: 32.5MB
class Solution {
    public double myPow(double x, int n) {
        double nD = n;
        if(n==0 || x==1){
            return 1;
        } else if(n<0) {
            x = 1/x;
            nD=(-1)*(double)n;
        }
        return positivePow(x,nD);
    }
    
    private double positivePow(double x, double n){
        if(n==1 || x==0 || x==1){
            return x;
        } else {
            if(n%2==0){
                //Even
                double halfPow = positivePow(x, n/2);
                return halfPow * halfPow;
            } else {
                //Odd
                double halfPow = positivePow(x, (n-1)/2);
                return halfPow * halfPow * x;
            }
        }
    }
}

Find more posts here.

Cheers & Chao!