LeetCode #50 Medium

Pow(x, n)

Implement pow(x, n), which computes x raised to the power n — including negative exponents — without the built-in power operator.

mathrecursiondivide and conquer

Open on LeetCode ↗

02

Intuition

💡

Multiplying x by itself n times is O(n). Instead, square the base and halve the exponent: x^n = (x^2)^(n/2). Each step throws away half the work, so it finishes in O(log n).

03

Approach

1

The naive loop is O(n)

Multiplying result by x exactly n times is correct but slow — for large n (up to ~2^31) that is far too many multiplications. The trick is that exponents split: x^n = (x^2)^(n//2), with one extra x left over when n is odd.

2

Square-and-halve (binary exponentiation)

Walk the exponent down toward zero. At each step, if the current exponent is odd, fold one factor of the current base into result. Then square the base and halve the exponent. This processes the exponent's binary representation bit by bit, so it runs in O(log n) multiplications instead of O(n).

3

Handle the negative power

A negative exponent just means a reciprocal: compute x^|n| with the loop above, then return 1 / result. Taking the absolute value up front keeps the loop logic identical for both signs.

04

Solution & live demo

python

▶1class Solution:
▶2    def myPow(self, x, n):
▶3        if n < 0:
▶4            x, n = 1 / x, -n
▶5        result = 1
▶6        while n > 0:
▶7            if n % 2 == 1:
▶8                result *= x
▶9            x *= x
▶10            n //= 2
▶11        return result

05

Edge cases

n = 0

Any base to the zero power is 1; the loop never runs and result stays 1.

Negative n

Compute the positive power, then take the reciprocal 1 / result.

x = 1 or x = -1 with huge n

Still O(log n); squaring stays at 1 or alternates sign correctly.

06

Complexity

Time

O(log n)

Space

O(1)

The exponent is halved every iteration, giving log n multiplications and constant extra space.