[Leetcode C++] Pow(x, n)


Implement pow(x, n).


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


class Solution {
    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;
            //check if n is positive or negative
            if(n>0) return val*val*x;
            else return val*val/x;

Leave a Reply

Your email address will not be published. Required fields are marked *