50. Pow(x, n) — DSA Atlas

MediumBit ManipulationDivide and conquer via bit decomposition of the exponentFast exponentiation (binary exponentiation)

Pow(x, n)

Implement myPow(x, n), which computes x raised to the integer power n (x^n). The exponent n may be negative, zero, or positive. Return the result as a floating-point number.

Open official problem prompt ↗

In plain English

Compute x^n exactly and fast, even when n is a huge (possibly negative) integer, without performing n separate multiplications.

Picture it like this

Doubling money: instead of adding one coin at a time, you keep doubling your pile (x, x^2, x^4, x^8, ...) and only cash in the piles whose 'bit' you actually need to reach the target power.

Example

Input: x = 2.00000, n = 10
Output: 1024.00000
Why: 2 multiplied by itself 10 times equals 1024.

Constraints

-100.0 < x < 100.0-2^31 <= n <= 2^31 - 1n is an integerEither x is not zero or n > 0-10^4 <= x^n <= 10^4

Pattern lesson

See the pattern, then code

Fast exponentiation (binary exponentiation)

↗

Bit Manipulation

XOR cancellation, powers of two, compact subset state, or per-bit counting.. x^n can be built from x^(n/2): if n is even, x^n = (x^(n/2))^2; if odd, x^n = x * (x^(n/2))^2. Reading n bit by bit, you square the running base each step and multiply it into the answer only where a bit of n is set.

New words, made simpleKnow these before the algorithm

Exponentiation by squaring: Building a power by repeatedly squaring the base and combining the pieces that correspond to set bits of the exponent.
Set bit: A bit position holding a 1; here it marks which powers-of-two chunks of the exponent must be multiplied in.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Naive repeated multiplication

With n up to ~2^31 this is far too slow and will time out.

Multiply x by itself n times in a loop.

Time O(n)Space O(1)

Best choiceBinary exponentiation

Only ~31 iterations for the largest input; the standard optimal solution.

Decompose the exponent into bits, square the base each step, and multiply into the answer on set bits.

Time O(log n)Space O(1)

The rule we keep true

Invariant

After processing the low k bits of n, result equals x0 raised to the value of those k bits, and x equals x0^(2^k) — the base ready for the next bit.

Why this is correct

Reasoning

Any exponent equals the sum of the powers of two at its set bits, so x^n is the product of x^(2^i) over those set bits i. Squaring the base each iteration produces exactly x^(2^i), and multiplying it in only on set bits assembles the full product.

The algorithm in three movesSay these aloud before coding

1If n is negative, replace x with 1/x and negate n

n=10 (1010b): bit0=0 skip, base=x^2

2Initialize result = 1 and iterate while n > 0

bit1=1 -> result*=x^2, base=x^4

3When the lowest bit of n is 1, multiply result by the current base x

bit2=0 skip, base=x^8; bit3=1 -> result*=x^8 = x^10

4Square the base x and shift n right by one bit

5Return result once all bits are consumed

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

10100

n=101

x^23

x^44

x^85

1 · Readx=2.0, n=10

2 · AskIs n negative?

3 · Update staten=10, result=1.0, base=2.0

4 · Resultn >= 0, no change

Key takeaway

10 in binary is 1010, so x^10 = x^8 * x^2 — only the set bits contribute a factor.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Handle negative exponents
x^(-n) = (1/x)^n, so invert the base once and work with a positive exponent.
2
Lines 6-11Squaring loop
Consume n bit by bit: multiply the result on set bits, square the base every iteration, and shift n right until it is zero.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

n = 0 returns 1.0 (loop body never runs)
Negative n such as -2, handled by inverting x
n = -2^31, whose negation still fits in Python's arbitrary-precision ints
x = 1 or x = -1 with large n

Common beginner mistakes

Forgetting to invert x for negative n
Overflow of -n in fixed-width languages when n = -2^31 (not an issue in Python but worth noting)
Using a plain O(n) loop and timing out
Initializing result as an int, which is fine in Python but should conceptually be a float

Check your understanding

Why does squaring the base every iteration line up with the bits of n?

Pow(x, n)

Pow(x, n)

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Bit Manipulation