Example 1
ready- Input
x = 2 n = 10- Expected
1024- Why
- repeated squaring reaches 2^10 in four halvings
Pow(x, n)
35 min · myPow()mediumOpen in LeetCode #50 ↗
Multiplying x by itself n times works for a small exponent. It falls apart when
n is two billion.
Given a floating-point number x—a number that may contain a fractional part—and
an integer n, return x raised to the power n. The exponent is the integer that
controls how copies of the base are multiplied or turned into a reciprocal.
A few ground rules:
- An exponent of
0produces1. - A negative exponent uses the reciprocal—one divided by the value:
x^(-n) = 1 / x^n. - Inputs are chosen so the real result is finite and stays within the stated range.
- Answers are compared with a tolerance—an allowed numerical gap—of
1e-5to account for floating-point rounding.
Constraints
-100.0 <= x <= 100.0-2^31 <= n <= 2^31 - 1- The true result lies within
[-10^4, 10^4].
Hints
Halve the work
For an even exponent, compute x^(n/2) once and square it. An odd exponent needs
one extra factor of x.
Read the exponent in bits
A binary digit is one 0 or 1 in an integer's base-two form. While halving
the exponent, multiply the answer by the current base only when that digit is 1.
Treat INT_MIN carefully
INT_MIN is the smallest signed 32-bit integer, -2^31. Its magnitude is 2^31,
which doesn't fit in a signed 32-bit integer.
Move the exponent into a wider numeric type before negating it; don't use a 32-bit
bitwise operation to take its absolute value.
Follow-up
Can you keep the logarithmic running time while using constant extra space?
Visible cases
Examples
Example 2
ready- Input
x = 2.1 n = 3- Expected
9.261- Why
- an odd exponent keeps one extra factor of 2.1
Example 3
ready- Input
x = 2 n = -2- Expected
0.25- Why
- the negative exponent takes the reciprocal of 2^2
Interview signal
Asked at
AmazonGoogleMeta
Recursive fast exponentiation
Fast exponentiation computes a power by halving the exponent instead of removing
one from it. Compute the half-power once, square it, and multiply by one extra x only
when the exponent is odd.
def my_pow(x: float, n: int) -> float:
def power(base: float, exponent: int) -> float:
if exponent == 0:
return 1.0
half = power(base, exponent // 2)
squared = half * half
return squared * base if exponent % 2 else squared
exponent = n
if exponent < 0:
x = 1.0 / x
exponent = -exponent
return power(x, exponent)Python integers expand to hold 2^31, so negating -2^31 is safe here. A
fixed-width integer uses a set number of bits. In a language with those integers,
widen n first and only then negate it. Negating INT_MIN inside a signed 32-bit value
overflows.
Time O(log |n|) because each call halves the exponent. Space O(log |n|) for the call stack, the memory that tracks unfinished recursive calls.
Iterative binary exponentiation
Binary exponentiation is the same halving idea written as a loop. base holds the
power for the current binary place, while result collects the places selected by odd
exponents.
def my_pow(x: float, n: int) -> float:
exponent = n
if exponent < 0:
x = 1.0 / x
exponent = -exponent
result = 1.0
while exponent > 0:
if exponent % 2 == 1:
result *= x
x *= x
exponent //= 2
return resultDon't halve with a 32-bit bitwise operator in JavaScript or TypeScript: that would
truncate the 2^31 magnitude back into a signed 32-bit value. Numeric division and
flooring preserve it exactly.
Time O(log |n|) for one iteration per binary digit. Space O(1) because the loop keeps only the current base, exponent, and result.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
1024
Run: visible + custom · Submit: full suite