Back to solutions

Pow(x, n)

MediumMath

Implement x raised to the power n (x^n), where n can be negative.

Open problem
Constraints
  • -100 < x < 100
  • -2^31 <= n <= 2^31 - 1

Fast exponentiation (binary)

Time O(log n)Space O(1)

Square the base and halve the exponent each step, multiplying the result when the current exponent bit is set. A negative exponent is handled by inverting the base.

double myPow(double x, int n) {
    long long e = n;
    if (e < 0) { x = 1 / x; e = -e; }
    double result = 1.0;
    while (e > 0) {
        if (e & 1) result *= x;
        x *= x;
        e >>= 1;
    }
    return result;
}