Skip to main content
DSA patterns

Pow(x, n)

mediumRecursion Must-doGoogleFacebookMicrosoft

Problem statement

You're given a real number x and an integer n. Return x raised to the power n — that is, x multiplied by itself n times, or, if n is negative, 1 divided by x raised to the positive version of n.

The catch is n: it can be as large as about 2.1 billion in either direction, so the obvious "multiply in a loop" answer is too slow, and negating the smallest possible n can overflow a normal 32-bit integer if you're not careful.

Examples

Example 1

Input: x = 2.00000, n = 10

Output: 1024.00000

Explanation: 2 multiplied by itself 10 times is 1024.

Example 2

Input: x = 2.10000, n = 3

Output: 9.26100

Explanation: 2.1 × 2.1 × 2.1 = 9.261.

Example 3

Input: x = 2.00000, n = -2

Output: 0.25000

Explanation: A negative exponent means "1 over" — 2⁻² is 1 / 2² = 1/4 =

Hints

Hint 1: Multiplying x by itself n times works, but what happens to that loop when n is close to 2 billion?

Approach

Optimal: Iterative binary exponentiation

Intuition

This does the exact same halving as the recursive version, but built from the bottom up instead of the top down, using the binary digits of n directly. Each bit of n (from least to most significant) says whether the current power of x (which keeps squaring itself) belongs in the answer.

It's the same trick every fast modular-exponentiation routine uses — walk the exponent's bits, square the base each step, and fold it into the result wherever a bit is set.

Steps

  1. Widen n to a 64-bit value; if it's negative, flip x to 1/x and make the exponent positive, exactly as in the recursive version.
  2. Start result at 1.0.
  3. While the exponent is greater than 0:
    • If its lowest bit is 1, multiply result by the current x.
    • Square x (this is what makes each step "worth" the next power of 2).
    • Shift the exponent right by one bit.
  4. Return result.

Dry run

x = 2.0, n = 10 (binary 1010)

N (binary) low bit result x after squaring
1010 0 1 4
0101 1 1 × 4 = 4 16
0010 0 4 256
0001 1 4 × 256 = 1024 65536
0000 — loop ends 1024 —

Edge cases: same as the recursive version — the 64-bit widening keeps n = INT_MIN from overflowing when it's negated.

Complexity

Time O(log n) - same cost as the recursive version: the exponent is halved (via a bit shift) once per iteration.

Space O(1) - no recursion stack, just the running result and a squared copy of `x`.

class Solution:
    def myPow(self, x: float, n: int) -> float:
        N = n
        if N < 0:
            x = 1 / x
            N = -N

        result = 1.0
        while N > 0:
            if N & 1:
                result *= x
            x *= x
            N >>= 1
        return result


if __name__ == "__main__":
    print(f"{Solution().myPow(2.00000, 10):.5f}")
    print(f"{Solution().myPow(2.10000, 3):.5f}")
    print(f"{Solution().myPow(2.00000, -2):.5f}")
RecapThe whole problem in a few lines, for the night before
  • Spot it: raise a number to a possibly huge (up to ~2³¹) integer
  • exponent, positive or negative
  • Idea: square-and-halve the exponent instead of multiplying one factor
  • at a time — xⁿ = (x^(n/2))², with one extra x folded in when n is odd
  • Cost: O(log n) time either way; O(log n) space recursively, O(1)
  • iteratively, versus O(n) time for the naive loop
  • Trap: negating the smallest possible 32-bit n overflows unless you
  • widen it to a 64-bit type first

Interview follow-ups

  • What if n could be a much larger number that doesn't fit in 64 bits — say, represented as a string of digits?

    The bit-by-bit halving trick still works, but you can't halve a huge decimal number the same way you halve a machine integer. Convert the exponent to binary digit-by-digit (repeated division by 2 on the big number, or parse it directly if it's given in binary), and drive the same square-and-multiply loop off those bits instead of a native integer's bits. The complexity becomes O(log n) squarings, each one costing whatever big-number multiplication costs.

  • How would you extend this to compute x^n mod m for a huge exponent, as used in cryptography?

    Take a modulus after every multiplication instead of letting the numbers grow — result = (result * x) % m and x = (x * x) % m at each step. This keeps every intermediate value bounded by m instead of exploding in size, which is exactly what makes RSA-style modular exponentiation practical for exponents with hundreds of digits.

  • What if you needed to answer many pow queries with the same x but different n values?

    Precompute x, x², x⁴, x⁸, … up to the largest power of two you'll need, once. Each query then just multiplies together the precomputed powers whose bit positions match the query's n, turning each individual query into O(log n) multiplications with no repeated squaring work across queries.

Frequently asked questions

The connection isn't searching — it's the halving. Binary search shrinks the range it's looking at by half each step; fast exponentiation shrinks the exponent by half each step. Both are divide-and-conquer recursions that turn a linear amount of work into a logarithmic amount by cutting the problem in half every time, which is why sheets that group by pattern often place them together.

A 32-bit signed integer's range is asymmetric: it can hold -2147483648 but its positive counterpart, 2147483648, is one more than the largest value the same type can hold (2147483647). Writing -n directly on the smallest possible n overflows. Copying n into a 64-bit long before negating sidesteps the whole issue, since the 64-bit range comfortably holds both.

The same halving trick — square-and-multiply — is the basis of the modpow/fast modular exponentiation used in RSA and Diffie-Hellman key exchange, so an interviewer using this problem is often checking whether you can recognize and implement that pattern, not just whether you can compute a power.

Both accumulate floating-point rounding error, but the fast approach does roughly log₂(n) multiplications instead of n, so it accumulates far less rounding error along the way — one more reason it's the better choice even ignoring speed.

Two, usually: forgetting the INT_MIN negation overflow, and forgetting that n = 0 should return 1.0 for any x, including x = 0 (the problem guarantees x isn't 0 when n could make that division undefined).