Pow(x, n)

You are given a floating-point number x and an integer n. Compute x raised to the power n — that is, x^n — without calling your language's built-in power function.

The exponent can be negative or zero:

x^0 = 1 for any valid input.
A negative exponent means repeated division: x^-n = 1 / x^n.

Return the result as a floating-point number.

Hints

· Stuck? Reveal one nudge at a time.

Multiplying x into a running product n times is correct — but n can be around two billion. What algebraic identity lets you skip most of those multiplications?

x^10 = (x^5)^2. If you already know x^5, one extra multiplication gives you x^10. Squaring the base doubles the exponent — so halving the exponent costs only one squaring.

Walk the exponent's binary digits: square the base every step, and multiply it into the answer whenever the current bit is 1. Handle n < 0 by flipping x to 1/x first — and negate n in a 64-bit variable, because -(-2^31) overflows 32 bits.

Common doubts

Because -n overflows: 2^31 does not fit in a 32-bit int, so negating -2^31 in place is undefined or wraps around. Copy the exponent into a 64-bit variable (or a plain number in Python/JavaScript) before negating.

Use the identity x^-n = (1/x)^n: replace x with 1 / x, make the exponent positive, and run the exact same loop. The statement guarantees you never face x = 0 with a negative n, so the division is always safe.

Not for correctness of the algorithm — both the loop and binary exponentiation accumulate only tiny rounding error over at most ~31 multiplications, and answers are compared with fixed decimal precision.

Because 1 is the multiplicative identity — the empty product. Starting at x silently adds one extra factor, which corrupts every even exponent and makes x^0 return x instead of 1.

Interview follow-ups

· What an interviewer asks next.

Same skeleton — binary exponentiation — but take the remainder after every multiplication: this is modular exponentiation, the core of RSA and Diffie-Hellman. The exponent can even arrive as a string of thousands of digits; you process its bits the same way.

Yes: pow(x, n) = pow(x*x, n/2), times x when n is odd — still O(log n) time but O(log n) stack. The iterative bit-walk is the same idea with O(1) space, so prefer it and mention the recursion as the cleaner-to-derive form.

Replace the number x with a 2x2 matrix: the n-th power of [[1,1],[1,0]] contains F(n). Binary exponentiation works over anything with associative multiplication — numbers, matrices, permutations.

Fun facts

Doubling-based multiplication appears in the Rhind papyrus from ancient Egypt (~1650 BC), and exponentiation by squaring shows up in Pingala's work on Sanskrit poetic meters over two thousand years ago — this may be the oldest algorithm you will ever implement.
Every HTTPS handshake your browser performs runs this exact square-and-multiply loop, just with huge integers under a modulus — binary exponentiation is quietly executed billions of times a day.
The square-and-multiply skeleton generalises to any associative operation: matrix powers for O(log n) Fibonacci, string repetition, even function composition.

Asked at

GoogleAmazonMetaMicrosoftAppleBloomberg

Frequently Sometimes Occasionally

Example 1

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3

Input: x = 2.00000, n = -2
Output: 0.25000
2^-2 = 1 / 2^2 = 1/4 = 0.25

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

Computing x^n looks like a one-liner — until you notice n can be around two billion. Multiplying one step at a time is far too slow, and the fix is one of the most reusable tricks in all of computing: squaring your way up instead of counting your way up. This tutorial takes you from the obvious loop to binary exponentiation in O(log n).

Prerequisites

Before you start

· Concepts used directly in the solution.

Exponent rules. Two identities do all the work here: x^(a+b) = x^a * x^b and x^-n = 1 / x^n.

Binary representation. Every exponent is a sum of powers of two — 10 = 8 + 2 — which is exactly what lets squaring replace counting.

Integer overflow. Negating the most negative 32-bit integer overflows; copying the exponent into a 64-bit variable first avoids the trap.

Understand the problem

In plain English: multiply x by itself n times — but do it fast enough that n ≈ 2 * 10^9 still finishes instantly. Formally: given a real x and an integer n (possibly negative or zero), return x^n, where x^-n = 1 / x^n and x^0 = 1.

Worked example — x = 2, n = 10

count up (brute):  2 → 4 → 8 → 16 → … → 1024      (10 multiplications)
double up (fast):  2 → 4 → 16 → 256 → 65536       (4 squarings)

n = 10 = 1010 in binary = 8 + 2
x^10 = x^8 · x^2 = 256 · 4 = 1024   ✓

Clarifying questions

Asking two or three sharp questions before typing signals that you design for the whole input space, not just the happy path.

Questions to ask first

· Signals seniority before you write a line of code.

Input range and sign

“Can the exponent n be negative or zero?”

Yes to both. x^0 = 1, and a negative exponent flips the base: x^-n = (1/x)^n. Normalising the sign up front keeps the core loop clean.

“Can x be negative?”

Yes — a negative base with an odd exponent gives a negative result, but the algorithm itself never changes.

Edge cases

“Can x be 0 while n is negative?”

No — the statement guarantees either x is non-zero or n > 0, so you never divide by zero.

“What about n equal to the most negative 32-bit integer?”

This is the classic trap: -n overflows a 32-bit int because 2^31 does not fit. Copy n into a 64-bit variable before negating.

Constraints and scale

“How large can n get?”

Up to about 2.1 * 10^9. An O(n) loop is billions of multiplications — hopeless. That single number tells you the interviewer wants O(log n).

The ideal opening — say it like this

Before I code, a few clarifying questions.

Can n be negative or zero — and if negative, I will compute one over x to the positive power?

Since n can be around two billion, a linear loop is too slow, so I will use binary exponentiation for O(log n).

One edge case I want to flag: negating the most negative 32-bit integer overflows, so I will hold the exponent in a 64-bit variable.

Key observations

1Aha

Squaring the base doubles the exponent

From x^(a+b) = x^a * x^b, setting a = b gives x^(2k) = (x^k)^2. One squaring buys you what would otherwise cost k extra multiplications.

x^10 = (x^5)^2        one multiplication, exponent halved

2Aha

Odd exponents peel off one factor

When the exponent is odd you cannot halve it cleanly — so peel one factor off first: x^5 = x · x^4. Now the remaining exponent is even and squaring applies again. Alternate peel and square and the exponent collapses to zero in O(log n) steps.

3Aha

The binary digits of n are the recipe

Write n in binary: 10 = 1010. Each 1 bit says multiply the current square into the answer; each squaring moves you to the next bit. About 31 iterations cover the entire 32-bit range — that is the whole algorithm.

Brute force vs optimal

	Brute force	Optimal
Time	O(n)	O(log n)
Space	O(1)	O(1)
n ≈ 2·10^9	billions of steps — TLE	about 31 steps

Full, runnable code for both approaches lives in the Approaches selector below.

Summary

Key takeaway

Halve the exponent, square the base. Binary exponentiation turns a linear count into a logarithmic ladder, and the same skeleton powers modular arithmetic, matrix exponentiation, and fast doubling everywhere.

if n < 0: x = 1/x, e = -n (in 64 bits)   else e = n
result = 1
while e > 0:
    if e is odd: result = result * x
    x = x * x
    e = e / 2 (integer division)
return result