Loading…

mediumMath GeometryLC #50Frequently asked

Pow(x, n)

Q: How do you solve Pow(x, n) using the Recursive Divide & Conquer approach?

When to use it: Lead with this — it makes the O(log n) recurrence visually obvious and is the easiest to explain on a whiteboard. The key algebraic identity is `xⁿ = (x^(n/2))²`. Computing the half-power **once** and squaring it does the work of the full power in a single extra multiply — and since the exponent halves every call, we reach the base case in `log₂ n` steps instead of `n`. **Why squaring the half is the whole speedup.** Naive exponentiation multiplies `x` into an accumulator `n` times — linear work. Divide-and-conquer instead asks: "what if I already knew `x^(n/2)`?" Then `xⁿ` is just that value squared. The recursion computes `half = pow(x, n/2)` once and reuses it twice via `half * half`, so each level of recursion does constant multiplications and there are only `log n` levels. That reuse — compute once, square — is the entire reason the exponent collapses logarithmically. **Handling odd exponents.** Integer division loses the remainder: for odd `n`, `n/2` rounds down, so `(x^(n/2))²` gives `x^(n-1)`. We're short exactly one factor of `x`, so we multiply it back: `n` odd → `x · half · half`. For even `n` no correction is needed. This is the recursive mirror of "multiply in only when the bit is 1". **The negative-exponent trap — and why `long` matters.** For `n < 0`, `xⁿ = 1 / x^|n|`. The obvious move is `n = -n`, then compute the positive power and reciprocate. But `n` can be `-2³¹ = -2147483648`, and `+2147483648` does **not** fit in a signed 32-bit int — negating it overflows and wraps right back to `-2147483648`, causing an infinite recursion or wrong sign. The fix is to widen `n` to a 64-bit `long` *before* negating, so `2147483648L` is representable. In Python integers are unbounded so this is a non-issue, but you must still call it out for the Java/C++ interviewer. Time complexity: O(log n). Space complexity: O(log n).

LCPractice

Math & Number Theory · 8 of 36 · 9 min

Implement pow(x, n), which calculates x raised to the power n (i.e., xⁿ).

x is a floating-point number and n is a signed 32-bit integer that may be negative.

In plain English

Raise a floating-point base x to an integer power n that can be negative or as large as ~2.1 billion. A loop of n multiplications is far too slow for big n, so we need the O(log n) doubling method. Negative n means a reciprocal, and n = -2³¹ has no positive counterpart in 32 bits — that edge case must be handled with a wider type.

Examples

Example 1

Input: x = 2.00000, n = 10
Output: 1024.00000
Note: 2¹⁰ = 1024.

Example 2

Input: x = 2.10000, n = 3
Output: 9.26100
Note: 2.1³ = 9.261.

Example 3

Input: x = 2.00000, n = -2
Output: 0.25000
Note: 2⁻² = 1 / 2² = 1 / 4 = 0.25.

Constraints

-100.0 < x < 100.0
-2³¹ ≤ n ≤ 2³¹ − 1 (n is a 32-bit signed integer)
n is an integer; either x is not zero or n > 0
-10⁴ ≤ xⁿ ≤ 10⁴

Clarifying questions4First question: Can n be negative?Explore questions

Q1.Can n be negative?
Yes. xⁿ for negative n is 1 / x^|n|. So compute the positive power and take the reciprocal.
Q2.How large can n get?
Up to 2³¹ − 1 ≈ 2.1 billion, and down to -2³¹. A naive O(n) loop would time out, and negating -2³¹ overflows a 32-bit int — handle with a long.
Q3.What is x⁰?
1 for any x by convention (the problem guarantees we never hit 0⁰ in a problematic way). The recursion/loop must bottom out returning 1.
Q4.Floating-point precision — exact or approximate?
Approximate is accepted; results within 10⁻⁵ are fine. We don't need exact decimal arithmetic.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Compute xⁿ in O(log n) using fast (binary) exponentiation: square the base and halve the exponent each step, multiplying the result in only when the current exponent bit is 1. Handle negative n by computing the positive power and returning its reciprocal — but convert n to a long FIRST, because negating INT_MIN (-2³¹) overflows a 32-bit int.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the O(log n) doubling trick instead of looping n times, can reason about associativity, and — critically — whether you spot the INT_MIN negation overflow when handling negative exponents.

Where candidates slip

Negating n with `n = -n` while n is still a 32-bit int, overflowing on n = -2³¹; or looping n times for an O(n) solution that times out on large exponents.

How to stand out

State the recurrence (x^n = (x^2)^(n/2)), explain why it's O(log n), promote n to long before negating, and mention the same pattern generalizes to modular and matrix exponentiation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive Divide & Conquer	`O(log n)`	`O(log n)`	Lead with this — it makes the O(log n) recurrence visually obvious and is the easiest to explain on a whiteboard.	Read
2	Iterative Binary Exponentiation (Optimal)Optimal	`O(log n)`	`O(1)`	Offer as the production-grade version: same O(log n) time but O(1) space and no stack-overflow risk on huge exponents.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCompute xⁿIs n small / bounded?YesNo (n up to 2³¹)Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursive Divide & Conquer

TimeO(log n)SpaceO(log n)

Lead with this — it makes the O(log n) recurrence visually obvious and is the easiest to explain on a whiteboard.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Naively xⁿ = x · x · … (n times) is O(n). Can you compute xⁿ from a SMALLER power so the work shrinks fast?

2Hint 2Explore hint

Note xⁿ = (x^(n/2))². If you compute the half-power once and square it, you halve the exponent each call — that's a log-depth recursion.

3Hint 3Explore hint

Handle odd n by peeling one factor: xⁿ = x · (x^(n/2))² when n is odd. And for negative n, compute x^|n| and return its reciprocal — but convert n to long before negating to dodge INT_MIN overflow.

A · Core idea

The key algebraic identity is xⁿ = (x^(n/2))². Computing the half-power once and squaring it does the work of the full power in a single extra multiply — and since the exponent halves every call, we reach the base case in log₂ n steps instead of n.

Why squaring the half is the whole speedup. Naive exponentiation multiplies x into an accumulator n times — linear work. Divide-and-conquer instead asks: "what if I already knew x^(n/2)?" Then xⁿ is just that value squared. The recursion computes half = pow(x, n/2) once and reuses it twice via half * half, so each level of recursion does constant multiplications and there are only log n levels. That reuse — compute once, square — is the entire reason the exponent collapses logarithmically.

Handling odd exponents. Integer division loses the remainder: for odd n, n/2 rounds down, so (x^(n/2))² gives x^(n-1). We're short exactly one factor of x, so we multiply it back: n odd → x · half · half. For even n no correction is needed. This is the recursive mirror of "multiply in only when the bit is 1".

The negative-exponent trap — and why `long` matters. For n < 0, xⁿ = 1 / x^|n|. The obvious move is n = -n, then compute the positive power and reciprocate. But n can be -2³¹ = -2147483648, and +2147483648 does not fit in a signed 32-bit int — negating it overflows and wraps right back to -2147483648, causing an infinite recursion or wrong sign. The fix is to widen n to a 64-bit long before negating, so 2147483648L is representable. In Python integers are unbounded so this is a non-issue, but you must still call it out for the Java/C++ interviewer.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x = 2.0, n = 10

Interactive diagram

Recursion tree halving the exponent

pow(2,10)

Active call / nodeSupporting contextReturned stateNot active

Each call halves n; depth is log₂ n. The half-power is computed once and squared.

Final result1024.0

C · Code with teaching comments

Reference implementation previewpublic double myPow(double x, int n) { long N = n; if (N < 0) { x = 1 / x; N = -N;Explore the full code

solution.javaJava

Recursive Divide & Conquer — reference

4 teaching notes

1
public double myPow(double x, int n) {
2
    // Promote to long BEFORE negating — -INT_MIN overflows a 32-bit int.
3
    long N = n;
4
    if (N < 0) {
5
        // Negative exponent → reciprocal base, then treat the exponent as positive.
6
        x = 1 / x;
7
        N = -N;
8
    }
9
    return fastPow(x, N);
10
}
11
 
12
private double fastPow(double x, long n) {
13
    if (n == 0) {
14
        return 1.0;
15
    }
16
    // Compute the half-power ONCE and reuse it — this is the O(log n) speedup.
17
    double half = fastPow(x, n / 2);
18
    if (n % 2 == 0) {
19
        return half * half;
20
    } else {
21
        // Odd exponent lost a factor in integer division — multiply x back in.
22
        return half * half * x;
23
    }
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(log n) timeO(log n) spaceOpen the invariant and proofExplore the proof

xⁿ = (x^(n/2))² is the divide-and-conquer heart: compute the subproblem once, square it, and the exponent halves every level. The odd-n correction (× x) and the negative-n reciprocal are the two bookkeeping details — and the long promotion before negating is the trap that separates a passing solution from a robust one.

ComplexityO(log n) time, O(log n) space — Each recursive call halves n, so the recursion depth is log₂|n|. One multiplication per level → O(log n) time. The call stack is log n deep → O(log n) space.

E · Edge cases and pitfalls5x = 2.0, n = -2147483648 — long N = n makes N = -2147483648; N = -N becomes 2147483648 (fits in long). Without the long, this overflows back to negative.Explore edge cases

Edge cases handled

x = 2.0, n = -2147483648long N = n makes N = -2147483648; N = -N becomes 2147483648 (fits in long). Without the long, this overflows back to negative.
x = 1.0, n = 21474836471 to any power is 1; recursion bottoms out quickly with all multiplications equal to 1.

Pitfalls

Negating n while it's still an int — overflow on n = -2³¹.
Recomputing pow(x, n/2) twice instead of storing it once — degrades to O(n).
Forgetting the odd-n extra ×x — gives x^(n-1) for odd exponents.

03.2

Approach 2 of 2 · Optimal

Iterative Binary Exponentiation (Optimal)

TimeO(log n)SpaceO(1)

Offer as the production-grade version: same O(log n) time but O(1) space and no stack-overflow risk on huge exponents.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write n in binary. xⁿ is the product of x^(2^k) for every bit k that is set in n. Can you accumulate that product while scanning the bits?

2Hint 2Explore hint

Keep a running `result = 1` and a `current = x`. Each step: if the lowest bit of n is 1, multiply `result *= current`; then square `current *= current` and shift n right (n /= 2).

3Hint 3Explore hint

Convert n to long and handle negativity up front (x = 1/x, n = -n). Loop while n > 0. This is the same math as the recursion but with no call stack.

A · Core idea

This is the same doubling math as the recursion, expressed by walking the binary representation of n. Every integer n is a sum of distinct powers of two — its set bits — so xⁿ is the product of x raised to each of those powers: x^(2^0), x^(2^1), x^(2^2), … We generate those squared powers on the fly and multiply in only the ones whose bit is set.

The two state variables. current starts at x and is squared every iteration, so it walks through x¹, x², x⁴, x⁸, … — exactly the x^(2^k) values. result starts at 1 and accumulates the answer. At each step we look at the lowest bit of n: if it's 1, the current squared power belongs in the product, so result *= current. Then we square current and shift n right by one bit (n /= 2) to examine the next bit. When n hits 0, every set bit has contributed and result holds xⁿ.

Why this equals the recursion. The recursive (x^(n/2))² and this square-current-each-step are two views of the same identity. Halving the exponent in the recursion corresponds to shifting n right by a bit here; squaring the half corresponds to squaring current. The iterative form just makes the exponent's binary structure explicit and drops the call stack — turning O(log n) space into O(1) space, which also removes any stack-overflow risk for exponents in the billions.

Negative exponent, same trap. As before, n < 0 means reciprocate: set x = 1/x and make n positive. And again, promote n to a long before negating so -2³¹ doesn't overflow. After that the loop is identical. This iterative skeleton is also the one you extend for modular exponentiation — just take % m after each multiply — and for matrix exponentiation by replacing scalar multiply with matrix multiply.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x = 2.0, n = 10

Interactive diagram

Picking the right approach

n=10 (1010)

Active call / nodeSupporting contextReturned stateNot active

The decision tree. Pow(x, n) needs the O(log n) doubling branch — looping n times times out.

Final result1024.0

C · Code with teaching comments

solution.javaJava

Iterative Binary Exponentiation (Optimal) — optimal

4 teaching notes

1
public double myPow(double x, int n) {
2
    // Widen before negating — -INT_MIN doesn't fit in a 32-bit int.
3
    long N = n;
4
    if (N < 0) {
5
        x = 1 / x;
6
        N = -N;
7
    }
8
    double result = 1.0;
9
    double current = x;
10
    while (N > 0) {
11
        // Lowest bit set means this power of two is part of n — include current in the
12
        // product.
13
        if ((N & 1) == 1) {
14
            result *= current;
15
        }
16
        // Square to move from x^(2^k) to x^(2^(k+1)) for the next bit.
17
        current *= current;
18
        // Shift right to examine the next exponent bit.
19
        N >>= 1;
20
    }
21
    return result;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

Reading n in binary makes the algorithm obvious: each set bit picks one squared power x^(2^k) to include. result collects the chosen powers, current marches through the powers of two by self-squaring. This O(1)-space loop is the template you reuse verbatim for modular and matrix exponentiation.

ComplexityO(log n) time, O(1) space — n has ~log₂ n bits; we do O(1) work per bit (a compare, maybe a multiply, a square, a shift). So O(log n) time and only a few scalar variables → O(1) space.

E · Edge cases and pitfalls6x = 2.0, n = 0 — Loop body never runs (0 > 0 false); result stays 1.0 — correct for x⁰.Explore edge cases

Edge cases handled

x = 2.0, n = 0Loop body never runs (0 > 0 false); result stays 1.0 — correct for x⁰.
x = 0.0, n = 5current = 0, result becomes 0 on the first set bit; returns 0.0.
x = 2.0, n = -2147483648long N negates safely to 2147483648; loop runs ~31 times. An int negation here would overflow.

Pitfalls

Negating n as an int — overflow on -2³¹ before the loop even starts.
Squaring current AFTER shifting n, or in the wrong order relative to the multiply — keep multiply, then square, then shift.
Using `result *= x` instead of `result *= current` — loses the doubling and gives wrong powers.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic double myPow(double x, int n) { long N = n; if (N < 0) { x = 1 / x; N = -N;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

INT_MIN negation overflow

n can be -2³¹. Negating it as a 32-bit int wraps back to -2³¹, causing infinite recursion or a wrong result. Promote to long first.

Explore the code comparison

Don't write this

if (n < 0) {
    x = 1 / x;
    n = -n; // overflow when n == Integer.MIN_VALUE
}

Write this instead

long N = n;
if (N < 0) {
    x = 1 / x;
    N = -N; // safe: 2147483648 fits in a long
}

O(n) loop times out

Multiplying x into an accumulator n times is linear; with n up to ~2.1 billion it TLEs. Use the log-n doubling instead.

Explore the code comparison

Don't write this

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

Write this instead

result, current = 1.0, x
while n > 0:
    if n & 1:
        result *= current
    current *= current
    n >>= 1

Recomputing the half-power

Calling pow(x, n/2) twice (once per occurrence of the square) doubles the recursion at every level, collapsing O(log n) back to O(n).

Explore the code comparison

Don't write this

return fastPow(x, n / 2) * fastPow(x, n / 2);

Write this instead

double half = fastPow(x, n / 2);
return half * half;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fast exponentiation — square the base, halve the exponent

Code pattern to memorize

xⁿ = (x²)^(n/2)        if n even
xⁿ = x · (x²)^(n/2)   if n odd
x⁻ⁿ = 1 / xⁿ
# in code: long N = n; if N<0: x = 1/x, N = -N

Rules to remember

1Promote n to a `long` before negating — -INT_MIN overflows a 32-bit int. This is THE bug interviewers wait for.
2For negative n, take the reciprocal: x⁻ⁿ = 1 / xⁿ. Either flip x = 1/x once at the start, or compute xⁿ and return 1 / result.
3Square the base, halve the exponent every iteration — that's what turns O(n) multiplications into O(log n).
4Multiply the running result in only when the exponent is odd (lowest bit set). Even exponents just keep squaring.
5n = 0 returns 1 for any x (including x = 0 by convention here). Make sure the loop/recursion bottoms out at 1.
6Iterative avoids stack overflow; recursive is cleaner to explain. Both are O(log n) — know both.

Use this pattern when

Raising to an integer power and naive O(n) multiplication is too slow
Exponent can be huge (10⁹+) — you need O(log n)
Modular exponentiation (a^b mod m) — same skeleton, mod each multiply
Any 'apply an associative operation n times' (matrix power, fast Fibonacci)

Choose another pattern when

Exponent is tiny / bounded by a small constant → a simple loop is fine and clearer
Base or exponent is floating/non-integer → use the library `pow` / logarithms
You only need x² or x³ → just multiply directly, no need for the trick
Language has a trusted bignum pow and the interview allows it

Interview takeaway

Binary exponentiation is the canonical 'do something n times in log n steps' tool: exploit that the operation is associative and that n's binary representation tells you exactly which squared powers to multiply. The same skeleton powers modular exponentiation, matrix exponentiation, and fast Fibonacci.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBinary (fast) exponentiation — the canonical divide-and-conquer for repeated associative operations. Recognise it whenever you must apply something n times and n is large: scalar power, modular power (a^b mod m), matrix power (fast Fibonacci). Square the operand, halve the exponent, multiply in on set bits.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Super Pow
Coming soon
Exponent is a huge array of digits — modular fast exponentiation, process digits with a^(10b+d) = (a^b)^10 · a^d.
Sqrt(x)
The inverse — find the integer whose square is ≤ x via binary search.
Count Good Numbers
Coming soon
Direct application of modular fast exponentiation under a prime modulus.
Fibonacci Number
Coming soon
Matrix exponentiation gives O(log n) Fibonacci using the same doubling skeleton.

Same pattern

←

Palindrome Number

Continue · Next problem

Sqrt(x)

mediumMath GeometryLC #50Frequently asked

Pow(x, n)

LCPractice

Math & Number Theory · 8 of 36 · 9 min

Implement pow(x, n), which calculates x raised to the power n (i.e., xⁿ).

x is a floating-point number and n is a signed 32-bit integer that may be negative.

In plain English

Examples

Example 1

Input: x = 2.00000, n = 10
Output: 1024.00000
Note: 2¹⁰ = 1024.

Example 2

Input: x = 2.10000, n = 3
Output: 9.26100
Note: 2.1³ = 9.261.

Example 3

Input: x = 2.00000, n = -2
Output: 0.25000
Note: 2⁻² = 1 / 2² = 1 / 4 = 0.25.

Constraints

-100.0 < x < 100.0
-2³¹ ≤ n ≤ 2³¹ − 1 (n is a 32-bit signed integer)
n is an integer; either x is not zero or n > 0
-10⁴ ≤ xⁿ ≤ 10⁴

Clarifying questions4First question: Can n be negative?Explore questions

Q1.Can n be negative?
Yes. xⁿ for negative n is 1 / x^|n|. So compute the positive power and take the reciprocal.
Q2.How large can n get?
Up to 2³¹ − 1 ≈ 2.1 billion, and down to -2³¹. A naive O(n) loop would time out, and negating -2³¹ overflows a 32-bit int — handle with a long.
Q3.What is x⁰?
1 for any x by convention (the problem guarantees we never hit 0⁰ in a problematic way). The recursion/loop must bottom out returning 1.
Q4.Floating-point precision — exact or approximate?
Approximate is accepted; results within 10⁻⁵ are fine. We don't need exact decimal arithmetic.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Negating n with `n = -n` while n is still a 32-bit int, overflowing on n = -2³¹; or looping n times for an O(n) solution that times out on large exponents.

How to stand out

State the recurrence (x^n = (x^2)^(n/2)), explain why it's O(log n), promote n to long before negating, and mention the same pattern generalizes to modular and matrix exponentiation.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive Divide & Conquer	`O(log n)`	`O(log n)`	Lead with this — it makes the O(log n) recurrence visually obvious and is the easiest to explain on a whiteboard.	Read
2	Iterative Binary Exponentiation (Optimal)Optimal	`O(log n)`	`O(1)`	Offer as the production-grade version: same O(log n) time but O(1) space and no stack-overflow risk on huge exponents.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursive Divide & Conquer

TimeO(log n)SpaceO(log n)

Lead with this — it makes the O(log n) recurrence visually obvious and is the easiest to explain on a whiteboard.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Naively xⁿ = x · x · … (n times) is O(n). Can you compute xⁿ from a SMALLER power so the work shrinks fast?

2Hint 2Explore hint

Note xⁿ = (x^(n/2))². If you compute the half-power once and square it, you halve the exponent each call — that's a log-depth recursion.

3Hint 3Explore hint

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x = 2.0, n = 10

Interactive diagram

Recursion tree halving the exponent

pow(2,10)

Active call / nodeSupporting contextReturned stateNot active

Each call halves n; depth is log₂ n. The half-power is computed once and squared.

Final result1024.0

C · Code with teaching comments

Reference implementation previewpublic double myPow(double x, int n) { long N = n; if (N < 0) { x = 1 / x; N = -N;Explore the full code

solution.javaJava

Recursive Divide & Conquer — reference

4 teaching notes

1
public double myPow(double x, int n) {
2
    // Promote to long BEFORE negating — -INT_MIN overflows a 32-bit int.
3
    long N = n;
4
    if (N < 0) {
5
        // Negative exponent → reciprocal base, then treat the exponent as positive.
6
        x = 1 / x;
7
        N = -N;
8
    }
9
    return fastPow(x, N);
10
}
11
 
12
private double fastPow(double x, long n) {
13
    if (n == 0) {
14
        return 1.0;
15
    }
16
    // Compute the half-power ONCE and reuse it — this is the O(log n) speedup.
17
    double half = fastPow(x, n / 2);
18
    if (n % 2 == 0) {
19
        return half * half;
20
    } else {
21
        // Odd exponent lost a factor in integer division — multiply x back in.
22
        return half * half * x;
23
    }
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(log n) timeO(log n) spaceOpen the invariant and proofExplore the proof

Edge cases handled

x = 2.0, n = -2147483648long N = n makes N = -2147483648; N = -N becomes 2147483648 (fits in long). Without the long, this overflows back to negative.
x = 1.0, n = 21474836471 to any power is 1; recursion bottoms out quickly with all multiplications equal to 1.

Pitfalls

Negating n while it's still an int — overflow on n = -2³¹.
Recomputing pow(x, n/2) twice instead of storing it once — degrades to O(n).
Forgetting the odd-n extra ×x — gives x^(n-1) for odd exponents.

03.2

Approach 2 of 2 · Optimal

Iterative Binary Exponentiation (Optimal)

TimeO(log n)SpaceO(1)

Offer as the production-grade version: same O(log n) time but O(1) space and no stack-overflow risk on huge exponents.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write n in binary. xⁿ is the product of x^(2^k) for every bit k that is set in n. Can you accumulate that product while scanning the bits?

2Hint 2Explore hint

Keep a running `result = 1` and a `current = x`. Each step: if the lowest bit of n is 1, multiply `result *= current`; then square `current *= current` and shift n right (n /= 2).

3Hint 3Explore hint

Convert n to long and handle negativity up front (x = 1/x, n = -n). Loop while n > 0. This is the same math as the recursion but with no call stack.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

x = 2.0, n = 10

Interactive diagram

Picking the right approach

n=10 (1010)

Active call / nodeSupporting contextReturned stateNot active

The decision tree. Pow(x, n) needs the O(log n) doubling branch — looping n times times out.

Final result1024.0

C · Code with teaching comments

solution.javaJava

Iterative Binary Exponentiation (Optimal) — optimal

4 teaching notes

1
public double myPow(double x, int n) {
2
    // Widen before negating — -INT_MIN doesn't fit in a 32-bit int.
3
    long N = n;
4
    if (N < 0) {
5
        x = 1 / x;
6
        N = -N;
7
    }
8
    double result = 1.0;
9
    double current = x;
10
    while (N > 0) {
11
        // Lowest bit set means this power of two is part of n — include current in the
12
        // product.
13
        if ((N & 1) == 1) {
14
            result *= current;
15
        }
16
        // Square to move from x^(2^k) to x^(2^(k+1)) for the next bit.
17
        current *= current;
18
        // Shift right to examine the next exponent bit.
19
        N >>= 1;
20
    }
21
    return result;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6x = 2.0, n = 0 — Loop body never runs (0 > 0 false); result stays 1.0 — correct for x⁰.Explore edge cases

Edge cases handled

x = 2.0, n = 0Loop body never runs (0 > 0 false); result stays 1.0 — correct for x⁰.
x = 0.0, n = 5current = 0, result becomes 0 on the first set bit; returns 0.0.
x = 2.0, n = -2147483648long N negates safely to 2147483648; loop runs ~31 times. An int negation here would overflow.

Pitfalls

Negating n as an int — overflow on -2³¹ before the loop even starts.
Squaring current AFTER shifting n, or in the wrong order relative to the multiply — keep multiply, then square, then shift.
Using `result *= x` instead of `result *= current` — loses the doubling and gives wrong powers.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic double myPow(double x, int n) { long N = n; if (N < 0) { x = 1 / x; N = -N;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

INT_MIN negation overflow

n can be -2³¹. Negating it as a 32-bit int wraps back to -2³¹, causing infinite recursion or a wrong result. Promote to long first.

Explore the code comparison

Don't write this

if (n < 0) {
    x = 1 / x;
    n = -n; // overflow when n == Integer.MIN_VALUE
}

Write this instead

long N = n;
if (N < 0) {
    x = 1 / x;
    N = -N; // safe: 2147483648 fits in a long
}

O(n) loop times out

Multiplying x into an accumulator n times is linear; with n up to ~2.1 billion it TLEs. Use the log-n doubling instead.

Explore the code comparison

Don't write this

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

Write this instead

result, current = 1.0, x
while n > 0:
    if n & 1:
        result *= current
    current *= current
    n >>= 1

Recomputing the half-power

Calling pow(x, n/2) twice (once per occurrence of the square) doubles the recursion at every level, collapsing O(log n) back to O(n).

Explore the code comparison

Don't write this

return fastPow(x, n / 2) * fastPow(x, n / 2);

Write this instead

double half = fastPow(x, n / 2);
return half * half;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fast exponentiation — square the base, halve the exponent

Code pattern to memorize

xⁿ = (x²)^(n/2)        if n even
xⁿ = x · (x²)^(n/2)   if n odd
x⁻ⁿ = 1 / xⁿ
# in code: long N = n; if N<0: x = 1/x, N = -N

Rules to remember

1Promote n to a `long` before negating — -INT_MIN overflows a 32-bit int. This is THE bug interviewers wait for.
2For negative n, take the reciprocal: x⁻ⁿ = 1 / xⁿ. Either flip x = 1/x once at the start, or compute xⁿ and return 1 / result.
3Square the base, halve the exponent every iteration — that's what turns O(n) multiplications into O(log n).
4Multiply the running result in only when the exponent is odd (lowest bit set). Even exponents just keep squaring.
5n = 0 returns 1 for any x (including x = 0 by convention here). Make sure the loop/recursion bottoms out at 1.
6Iterative avoids stack overflow; recursive is cleaner to explain. Both are O(log n) — know both.

Use this pattern when

Raising to an integer power and naive O(n) multiplication is too slow
Exponent can be huge (10⁹+) — you need O(log n)
Modular exponentiation (a^b mod m) — same skeleton, mod each multiply
Any 'apply an associative operation n times' (matrix power, fast Fibonacci)

Choose another pattern when

Exponent is tiny / bounded by a small constant → a simple loop is fine and clearer
Base or exponent is floating/non-integer → use the library `pow` / logarithms
You only need x² or x³ → just multiply directly, no need for the trick
Language has a trusted bignum pow and the interview allows it

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Super Pow
Coming soon
Exponent is a huge array of digits — modular fast exponentiation, process digits with a^(10b+d) = (a^b)^10 · a^d.
Sqrt(x)
The inverse — find the integer whose square is ≤ x via binary search.
Count Good Numbers
Coming soon
Direct application of modular fast exponentiation under a prime modulus.
Fibonacci Number
Coming soon
Matrix exponentiation gives O(log n) Fibonacci using the same doubling skeleton.

Same pattern

←

Palindrome Number

Continue · Next problem

Sqrt(x)