Pow(x, n)

Implement pow(x, n).

Recursive solution is easier to understand. It uses the divide-and-conquer approach, which also runs in $Theta(lg n)$ time. The formula is shown below:

$x^n=\begin{cases}1.0&\text{if } n=0,\\ x^{n/2}\cdot x^{n/2}&\text{if }n\ne0\text{ and }n\text{ is even,}\\ x^{\lfloor n/2\rfloor}\cdot x^{\lfloor n/2\rfloor}\cdot x&\text{if }n>0\text{ and }n\text{ is odd,}\\ x^{\lceil n/2\rceil}\cdot x^{\lceil n/2\rceil}\cdot x^{-1}& \text{if }n<0\text{ and }n\text{ is odd.}\end{cases}$

And the code is quite simple and straightforward.

Code:

class Solution {
public:
    double pow(double x, int n) {
        if(n==0)
            return 1;
        double half=pow(x,n/2);
        if(n%2==0)
            return half*half; // n is even (both neg and pos)
        else if(n>0)
            return half*half*x; // n is odd and pos
        else
            return half*half/x; // n is odd and neg
    }
};

Approach 2:

Consider the binary representation of n. For example, if it is "10001011", then x^n = x^(1+2+8+128) = x^1 * x^2 * x^8 * x^128. Thus, we don't want to loop n times to calculate x^n. To speed up, we loop through each bit, if the i-th bit is 1, then we add x^(1 << i) to the result. Since (1 << i) is a power of 2, x^(1<<(i+1)) = square(x^(1<<i)). The loop executes for a maximum of log(n) times.

Code:

class Solution {
public:
    double pow(double x, int n) {
        unsigned m = abs((double)n);
        double ret = 1;
        for ( ; m; x *= x, m >>= 1) {
            if (m & 1) {
                ret *= x;
            }
        }
        return (n < 0) ? (1.0 / ret) : (ret);
    }
};