47. Pow(x, n)

Square the base repeatedly and multiply it into the result only for the set bits of the exponent. This computes x^n in O(log n) multiplications instead of n. Negative exponents just invert the base first.

Idea

Computing x^n by multiplying n times is O(n). Instead, use the binary representation of n: x^n is the product of x^(2^k) for each set bit k. We repeatedly square x (giving x, x², x⁴, x⁸, …) and multiply the current square into the answer whenever the corresponding bit of n is 1.

A negative exponent is handled by replacing x with 1/x and negating n.

Algorithm

1. If n < 0, set x = 1/x and n = -n.
2. result = 1. While n > 0:
   • If the lowest bit of n is set, result *= x.
   • Square: x *= x; shift n >>= 1.
3. Return result.

Worked example: x = 2, n = 10 (binary 1010)

Result: 1024 (bits 1 and 3 of 10 are set → 4 × 256).

Complexity

• Time: O(log n).
• Space: O(1).

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