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).

How to spot this pattern

Exponentiation by squaring: halve the exponent each round instead of decrementing it, turning O(n) into O(log n). The binary expansion of n is what the loop is really reading — each n % 2 asks whether the current squared value belongs in the product. The same doubling idea powers modular exponentiation and matrix power.

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

▶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

Common pitfalls

Multiplying in a loop n times

✗ Wrong

for _ in range(n):
    result *= x

✓ Right

while n > 0:
    if n % 2 == 1: result *= x
    x *= x
    n //= 2

With n up to 2^31 that's billions of iterations. Squaring the base while halving the exponent reaches the same answer in about 31 steps.

Negating the exponent without inverting the base

✗ Wrong

if n < 0:
    n = -n

✓ Right

if n < 0:
    x, n = 1 / x, -n

A negative exponent means the reciprocal, so flipping only the sign computes x^|n| and returns a number that is wrong by a factor of x^(2n). Both must change together.

Squaring only when the bit is set

✗ Wrong

if n % 2 == 1:
    result *= x
    x *= x
n //= 2

✓ Right

if n % 2 == 1: result *= x
x *= x
n //= 2

x tracks base^(2^k) and must double on every iteration to stay aligned with the bit position. Squaring conditionally desynchronises it from n, so later bits multiply in the wrong power.

06

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.

07

Complexity

Time

O(log n)

Space

O(1)

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