MediumMathRecursionUpdated Sep 2026

50. Pow(x, n)

Asked at Oracle, Walmart, Bloomberg

Difficulty

Medium

Time

O(log n)

Space

O(1)

Pattern

Math

Companies

3

Problem

Implement a function that computes x raised to the power n, that is x^n.

x is a floating-point number and n is an integer. n may be negative, in which case the answer is the reciprocal: x^(-n) = 1 / x^n. n may also be 0, and then the answer is 1.

The catch is size. n can be as large as about 2 billion, so multiplying x by itself n times is far too slow. You need a method that finishes in about 31 steps, no matter how big n is.

What we are computing

x = 2, n = 102 * 2 * ... * 2 (10 times)answer = 1024The naive idea: multiply x by itself n timesx = 2, n = -2flip: 1 / 2^2answer = 0.25A negative exponent just means take the reciprocal
We want x multiplied by itself n times, and a negative n flips the answer into 1 over that product.

Constraints

  • ●-100.0 < x < 100.0
  • ●-2^31 <= n <= 2^31-1
  • ●n is an integer
  • ●Either x is not zero or n > 0
  • ●-10^4 <= x^n <= 10^4

Examples

Example 1
Inputx = 2.00000, n = 10
Output1024.00000
Why2 multiplied by itself 10 times gives 1024.
Example 2
Inputx = 2.10000, n = 3
Output9.26100
Why2.1 * 2.1 = 4.41, and 4.41 * 2.1 = 9.261.
Example 3
Inputx = 2.00000, n = -2
Output0.25000
WhyA negative exponent means take the reciprocal: 2^-2 = 1 / 2^2 = 1 / 4 = 0.25.

Asked At

3 companies
CompanyDifficulty
OracleMediumView all Oracle questions →
WalmartMediumView all Walmart questions →
BloombergMediumView all Bloomberg questions →

How to Think About It

1

Naive: multiply x by itself n times. O(n). Too slow for large n.

2

Fast exponentiation: x^n = (x^(n/2))^2 if n is even, x * x^(n-1) if n is odd. This halves the problem each step → O(log n).

3

Why it works: x^8 = (x^4)^2 = ((x^2)^2)^2. You only need 3 squarings instead of 7 multiplications.

4

Handle negative n: x^(-n) = 1 / x^n. Convert n to positive and flip the result.

5

Edge cases: n=0 (return 1), n=1 (return x), x=0, n=INT_MIN (special case to avoid overflow when negating).

Optimal Approach

Recursive:
Step 1: Base case — if n == 0, return 1.
Step 2: If n is odd: result = x * pow(x, n-1).
Step 3: If n is even: result = pow(x, n/2) ^ 2.
Step 4: If n < 0: x = 1/x, n = -n.

Iterative (bit manipulation):

  • If n is negative, flip x to 1/x and n to -n.
  • For each bit in n: if bit is 1, multiply result by current x. Square x at each step.

Time: O(log n) — n is halved at each step. Space: O(log n) recursive, O(1) iterative.

Square and halve

n in binary84211010n = 10 = 1010 in binary, so bits 8 and 2 are setbit 0: skip, x = 2^2 = 4bit 1: result *= 4, x = 4^2 = 16bit 0: skip, x = 16^2 = 256bit 1: result *= 256, x = 256^2result = 4 * 256 = 1024if n is odd: result *= xx = x * xn = n // 2
We read the bits of n from the bottom. When a bit is 1 we fold the current x into the result, and we square x every step.
ComplexityTime O(log n)Space O(1)Each loop iteration halves n, so there are about log2(n) iterations, and the iterative version keeps only a few variables.

What Trips People Up in Real Interviews

1

Using the naive O(n) loop. The interviewer expects O(log n) fast exponentiation. Squaring at each step halves the exponent.

2

Not handling negative exponents. If n < 0, compute 1 / pow(x, -n). Flip the sign and invert the base.

3

Integer overflow when negating INT_MIN. n = -INT_MIN overflows in 32-bit. Use long or handle the edge case separately.

4

Forgetting that x^0 = 1 for any x (including 0). The base case must return 1 when n == 0.

5

Using recursion without memoization. The recursive approach is O(log n) because each call halves n. No memoization needed.

Solution Code

O(log n) time
def myPow(x, n):
    if n == 0:
        return 1.0
    if n < 0:
        x = 1 / x
        n = -n
    result = 1.0
    while n > 0:
        if n % 2 == 1:
            result *= x
        x *= x
        n //= 2
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Pow(x, n) problem?

Implement `pow(x, n)` which calculates x raised to the power n. The `fast exponentiation` approach reduces time from `O(n)` to `O(log n)` by squaring.

How do you solve Pow(x, n)?

The optimal approach runs in O(log n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Pow(x, n)?

Pow(x, n) is asked at Oracle, Walmart, Bloomberg. It is a medium difficulty problem.

What are common mistakes on Pow(x, n)?
  • Using the naive `O(n)` loop. The interviewer expects `O(log n)` fast exponentiation. Squaring at each step halves the exponent.
  • Not handling negative exponents. If n < 0, compute `1 / pow(x, -n)`. Flip the sign and invert the base.
  • Integer overflow when negating INT_MIN. `n = -INT_MIN` overflows in 32-bit. Use `long` or handle the edge case separately.
  • Forgetting that `x^0 = 1` for any x (including 0). The base case must return 1 when n == 0.
  • Using recursion without memoization. The recursive approach is `O(log n)` because each call halves n. No memoization needed.