Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Pow(x, n)
• Main tags: Math, Recursion

What the problem is really asking

The task is to compute x^n, but the real constraint is not the arithmetic itself. It is that n can be very large, including negative values, so a straightforward loop that multiplies x by itself |n| times is too slow.

This is really a problem about finding a smarter way to reuse work. The moment the exponent gets big, the interview is testing whether the candidate sees the binary structure inside exponentiation.

Why the obvious solution is not enough

The brute-force idea is simple:

• if n is positive, multiply x by itself n times
• if n is negative, compute x^|n| and invert the result

That works for correctness, but it costs O(|n|) multiplications.

That is the issue. If n is huge, doing one multiplication per unit of exponent is unnecessary. Most of that work is repetitive, because powers like x^8, x^16, and x^32 can be built by squaring smaller powers that have already been computed.

The key insight

The optimal idea is exponentiation by squaring.

There are two identities that matter:

• if n is even, then x^n = (x^2)^(n / 2)
• if n is odd, then x^n = x * x^(n - 1)

Those two facts combine beautifully. Instead of shrinking the exponent by 1 every step, the algorithm usually cuts it in half. That is what changes the runtime from linear to logarithmic.

Another important transformation is for negative exponents:

x^(-n) = 1 / x^n

So the full plan is:

1. If the exponent is negative, flip the base to its reciprocal and make the exponent positive.
2. Repeatedly square the current power.
3. Use the binary digits of the exponent to decide when that current power should be multiplied into the answer.

How to derive the optimal solution in an interview

A clean interview path usually looks like this:

1. Start with the brute-force multiplication approach.
2. Notice that powers double naturally: x^2, x^4, x^8, x^16.
3. Realize that any exponent can be written in binary, so the final answer is a product of selected doubled powers.
4. Turn that observation into a loop: if the current exponent bit is 1, multiply the running answer by the current power; then square the current power and shift the exponent right by one bit.

For example, if n = 13, then 13 in binary is 1101.

That means:

x^13 = x^8 * x^4 * x^1

The loop builds exactly those powers by repeated squaring and multiplies in only the ones whose bits are set.

Best approach

The best final answer for this problem is the iterative exponentiation-by-squaring version.

• Time: O(log |n|)
• Extra space: O(1)

There is also a recursive version with the same time complexity, but the iterative one is usually better in interviews because it is explicit, avoids call-stack overhead, and makes the bit logic easy to explain.

Python solution

The implementation below separates the work into small pieces:

• one helper normalizes negative exponents
• one helper performs binary exponentiation for a non-negative exponent
• the Solution wrapper stays thin and interview-friendly

The important invariant is:

result * current_factor^remaining_exponent

always equals the original target value. Each loop iteration preserves that invariant while making remaining_exponent smaller.

from typing import Tuple


def normalize_base_and_exponent(base: float, exponent: int) -> Tuple[float, int]:
    """
    Convert the problem into an equivalent one with a non-negative exponent.

    Example:
    2^-3 becomes (1/2)^3.
    """
    if exponent >= 0:
        return base, exponent

    if base == 0:
        raise ValueError("0 cannot be raised to a negative exponent.")

    return 1.0 / base, -exponent


def power_with_binary_exponentiation(base: float, exponent: int) -> float:
    """
    Compute base ** exponent for a non-negative integer exponent.

    The loop walks through the exponent bits from least significant to most
    significant. `current_factor` stores the current power of the base:
    base, base^2, base^4, base^8, and so on.
    """
    result = 1.0
    current_factor = base
    remaining_exponent = exponent

    while remaining_exponent > 0:
        if remaining_exponent & 1:
            result *= current_factor

        # Move from base^(2^k) to base^(2^(k + 1)).
        current_factor *= current_factor
        remaining_exponent >>= 1

    return result


def compute_power(base: float, exponent: int) -> float:
    """Return base ** exponent using O(log |exponent|) multiplications."""
    normalized_base, normalized_exponent = normalize_base_and_exponent(
        base=base,
        exponent=exponent,
    )

    return power_with_binary_exponentiation(
        base=normalized_base,
        exponent=normalized_exponent,
    )


class Solution:
    def myPow(self, x: float, n: int) -> float:
        """LeetCode entry point."""
        return compute_power(base=x, exponent=n)

This works in O(log |n|) time because every loop iteration halves the remaining exponent. The extra space stays O(1) because the algorithm uses only a fixed number of variables.

Interview follow-ups

Can you write the recursive version too?

Yes. The recursive formulation follows the same math directly. If n == 0, return 1. Otherwise compute half = pow(x, n // 2), then return half * half when n is even, or half * half * x when n is odd. Negative exponents are still handled by converting the problem into 1 / pow(x, -n). This works because the recurrence keeps dividing the exponent by 2, so the depth is only O(log |n|). The tradeoff is space: recursion uses O(log |n|) call-stack frames, while the iterative version stays at O(1) extra space.

What changes if the interviewer asks for x^n mod m?

The same repeated-squaring idea still applies. The only change is that every multiplication is followed by a modulo operation, so values never grow unnecessarily large. The core loop becomes result = (result * current_factor) % m and current_factor = (current_factor * current_factor) % m. That still works because modular multiplication is compatible with exponentiation, and the binary decomposition of the exponent has not changed. The complexity remains O(log n) time and O(1) extra space. The main caveat is negative exponents: in modular arithmetic they are only valid when a modular inverse exists, which depends on the base and the modulus.

How would you justify correctness without hand-waving?

The strongest explanation is a loop invariant. At the start of every iteration, result * current_factor^remaining_exponent equals the original target value. If the low bit of remaining_exponent is 1, the algorithm moves one copy of current_factor from the power term into result. Then it squares current_factor and halves remaining_exponent, which preserves the same total value because (a^2)^k = a^(2k). When remaining_exponent finally reaches 0, the power term becomes 1, so result alone must equal the answer. This proof is concise, rigorous, and usually more convincing than tracing a few examples.

What about overflow or precision issues in other languages?

That depends on what the interviewer cares about. In Python, large integers are arbitrary precision, but this problem uses floating-point input, so the practical limitation is floating-point precision rather than integer overflow. In fixed-width languages such as Java or C++, repeated squaring can overflow quickly for integer variants of the problem, so the implementation may need a wider type, modular arithmetic, or explicit overflow checks depending on the specification. The algorithmic idea does not change, but the data-type story becomes part of the answer. That is an important tradeoff to mention in a real interview, because asymptotically optimal code can still be numerically unsafe if the value range is ignored.

Takeaway

The heart of this problem is recognizing that exponents should be processed in binary, not one step at a time. Once that clicks, the optimal solution is short, fast, and easy to defend: halve the exponent every round, square the current factor, and multiply into the result only when the current bit says that power is needed.