Pow(x, n)
A medium Math interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Math
- Sheets
- 2
- Core for
- 13 roles
The problem
Compute x to the power n yourself, without a library power function. The exponent n can be positive, zero or negative, and the approach should use far fewer than n multiplications for large n.
Example 1
- Input
- x = 2.0, n = 10
- Output
- 1024.0
- Why
- 2^10 = 1024.
Example 2
- Input
- x = 2.1, n = 3
- Output
- 9.261
- Why
- 2.1^3 = 2.1 * 2.1 * 2.1 = 9.261.
Example 3
- Input
- x = 2.0, n = -2
- Output
- 0.25
- Why
- 2^(-2) = 1 / 2^2 = 1/4 = 0.25.
Example 4
- Input
- x = 0.00001, n = 2147483647
- Output
- 0.0
- Why
- A very small base raised to a very large power approaches 0.
Constraints
- -100.0 < x < 100.0
- -2^31 <= n <= 2^31 - 1
- -10^4 <= x^n <= 10^4
How to think about it
Updated 2026-09-29Multiplying x by itself one step at a time is far too slow for exponents near 2 × 10^9. Instead, note that x^n equals (x^2)^(n/2) for even exponents and x × x^(n-1) for odd ones, halving the remaining exponent at every step and converting linear work into logarithmic steps.
Approaches, worst first
Linear multiplicative loop
time O(|n|) · space O(1)
Iterate |n| times multiplying an accumulator by x. When n reaches 2^31 - 1, running billions of multiplications causes a timeout.
Binary exponentiationWrite this one
time O(log |n|) · space O(1)
Maintain base x and result 1.0. While n > 0, if the lowest bit of n is 1, multiply result by current base; then square the base and shift n right by 1. For negative n, invert the base and negate n safely.
Where people lose marks · 3
- Negating n when n is -2^31: in 32-bit signed integers, -(-2^31) cannot be represented and overflows; cast n to a 64-bit integer before negating.
- Dividing by zero when base x is 0.0 with a negative exponent.
- Precision loss from repeatedly computing 1 / x; inverting the accumulated result once at the end is more stable than repeatedly multiplying by (1 / x).
The theory behind it
Math — the ground this problem stands on. All Math problems
What Math is
Algorithmic math is the application of number properties, modular arithmetic, and geometric patterns to compute results without simulating every step. Rather than filling memory buffers with millions of simulated counters or walking endless loops, mathematical formulation uses identities like prime factorization, digit extraction, and greatest common divisors to jump directly to target answers through closed-form rules.
When to reach for it
Reach for mathematical techniques when problem bounds are massive, such as constraints reaching ten to the eighteenth power where simulation is impossible. Strong prompts mention prime generation, greatest common divisor calculations, modular inverses, fast exponentiation, digit reversals, or combinatorial arrangements. If brute-force counting produces memory overflow or time limit exceeded warnings, algebraic reorganization is the intended path.
How the pattern works
Focus on numeric constraints and potential overflows before writing expressions. Break numbers into constituent digits using modulo ten to peel least significant figures and integer division to shrink scale. For divisibility, apply Euclid's remainder theorem repeatedly until remainder drops to zero. Apply modulo arithmetic at every intermediate addition and multiplication stage rather than once at the end, preventing values from spilling beyond standard numeric register limits.
More Math problems
Target Roles
Core requirement for 13 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .