Implementing pow(x, n)

double myPow(double x, int n) {
    double res = 1.0;
    for(int i = n; i != 0; i /= 2) {
        // multiply once if odd, even numbers always divide down to 1
        if (i % 2 != 0) res *= x;
        x *= x;
    }

    return n < 0 ? 1 / res : res;
}

This implements the power function efficiently using binary exponentiation. Instead of multiplying x by itself n times, it cuts the problem in half each iteration. When the exponent is odd, we multiply the result by x once. Then we square x and halve the exponent. This gives us O(log n) performance instead of O(n).

The code handles negative exponents by computing the positive power first, then returning its reciprocal when n is negative.

#interview #tencent #math