Pow(x, n)

MediumMath & GeometryNeetCode 150MidOpen on LeetCodeUpdated Nov 11, 2026

Implement pow(x, n), which returns x raised to the integer power n. x is a floating-point number, and n can be negative, zero, or positive. n can be as large as about two billion in magnitude, so aim for far fewer than n multiplications.

Examples

x = 3.0, n = 5 returns 243.0

3^5 = 243. Squaring gives 3^2 = 9 and 3^4 = 81, and 3^5 = 3^4 * 3, so a few multiplications replace five.

x = 2.0, n = -3 returns 0.125

A negative exponent means the reciprocal: 1 / 2^3 = 1 / 8.

x = 0.5, n = 0 returns 1.0

Any nonzero x raised to the power 0 is 1.

Constraints

-100.0 < x < 100.0
-2^31 <= n <= 2^31 - 1
Either x is nonzero or n > 0.
-10^4 <= x^n <= 10^4

Hints

Hint 1

Multiplying x by itself n times is O(n), and n can be about two billion. How can x^8 take fewer than seven multiplications?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Use exponentiation by squaring. Written in binary, n is a sum of powers of two, so x^n is the product of x^(2^k) for every bit k that is set. Keep a base that starts at x and squares itself each step, multiply it into the result whenever the lowest remaining bit of n is 1, and shift n right. For a negative n, replace x with 1 / x and n with -n first. Do that negation in a 64-bit integer, because -(-2^31) doesn't fit in a 32-bit int. O(log |n|) time and O(1) space.

Time

O(log n)

Space

O(1)

Pitfall

Negating n in a 32-bit int. When n is -2^31, -n overflows back to -2^31 and the loop never sees a positive exponent. Copy n into a long before negating it.

Solutions

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

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x, n = 1 / x, -n
        result = 1.0
        while n:
            if n & 1:
                result *= x
            x *= x
            n >>= 1
        return result