Problem

Implement pow(x, n).

Analysis

Divide and conquer, first compute pow(x, n/2), then use it to compute pow(x,n). Need to consider
– n is odd or even
– if n is odd, need to consider n is positive or negative

Solution

class Solution {
public:
    double myPow(double x, int n) {
        if(x==0) return 0;
        if(n==0) return 1;
        
        //divide and conquer
        int half = n/2;
        double val = myPow(x, half);
        //check if n is odd or even
        if(n%2 == 0)
            return val*val;
        else{
            //check if n is positive or negative
            if(n>0) return val*val*x;
            else return val*val/x;
        }
        
    }
};