Problem statement
Implement myPow(x,n) to return a double representing x raised to the integer exponent n. Positive powers multiply factors of x; a negative power uses the reciprocal: 2^-2 = 1/4.
The LeetCode contract uses a signed 32-bit exponent and excludes zero when n is nonpositive. The supplied source includes a six-decimal display instruction, but formatting is separate from returning a double. The teaching driver prints the numerical result directly.
Constraints & requirements
- CONTRACT
- Use a 32-bit int exponent. Valid input excludes zero with a nonpositive exponent. Convert n to long before negating Integer.MIN_VALUE. Decimal formatting is a driver concern.
Examples 3 test cases
Example 1 Case 1
- Input
x=2.0; n=10- Output
1024.0
Halving needs only a short chain of calls instead of ten repeated factors.
Example 2 Case 2
- Input
x=2.0; n=-2- Output
0.25
Use the reciprocal base and positive exponent.
Example 3 Case 3
- Input
x=-1.0; n=-2147483648- Output
1.0
The smallest int exponent has an even positive magnitude that fits long.
Hints Optional
01Hint 1
Express x^n using x^(n/2).
02Hint 2
Compute the smaller power once; square it and add x only for odd n.
03Hint 3
Widen the exponent before negation; Java evaluates -n as int if n is int.
How to think before coding
Define positivePower(x,k) for a nonnegative exponent. k==0 returns the multiplicative identity 1. One child calculates x^(k/2); squaring supplies the even part, and k%2 decides whether one extra x is needed. Store that child result: calling the helper twice discards the reuse that makes the method logarithmic. Normalize a negative exponent in the public wrapper.
Brute force and the improvement
Multiply x by itself |n| times; for a negative exponent, use the reciprocal base and positive magnitude. This costs O(|n|) time and O(1) extra space, and is a useful small-input oracle. It is far too much repeated work for a large exponent. Compute the half power ONCE, square it, and multiply by x only for an odd exponent. Halving reaches O(log |n|) calls. Widen the int exponent to long BEFORE negating it, including Integer.MIN_VALUE.
Intuition: reuse a smaller answer
For 2^10, calculate 2^5 once and square it. For 2^5, calculate 2^2, square it, then multiply by one extra 2.
For nonnegative n, integer division gives n = 2·floor(n/2) + (n mod 2). That explains both cases. Even exponents need only the square; odd exponents need one extra factor. Each child solves an exponent about half as large, so the call chain shrinks quickly.
This is not a binary recursion tree. Calling pow(x,n/2) twice throws away reuse and changes the time bound. Store the returned value in half and multiply it by itself.
Algorithm
- Copy the int exponent into a long.
- If it is negative, replace x with
1/xand negate the long exponent. - Return 1 when the remaining exponent is zero.
- Recursively find the half power once.
- Square it; multiply by x only for an odd exponent.
Java solution
Convert the exponent to long before negating it. Passing an already-overflowed -n into a long parameter would be too late for Integer.MIN_VALUE.
import java.util.*;
class Solution {
public static double myPow(double x, int n) {
long exponent = n; // Widen BEFORE negation: -Integer.MIN_VALUE does not fit in int.
if (exponent < 0) {
x = 1.0 / x; // x^(-k) equals (1/x)^k; valid input excludes zero with negative power.
exponent = -exponent; // Safe now, including the exponent -2,147,483,648.
}
return positivePower(x, exponent); // This helper sees only nonnegative exponents.
}
private static double positivePower(double x, long n) {
if (n == 0) return 1.0; // Multiplication identity: no factors remain.
double half = positivePower(x, n / 2); // Compute the smaller power ONCE, not twice.
double square = half * half; // Supply 2 * floor(n/2) factors of x.
return n % 2 == 0 ? square : square * x; // An odd exponent needs one extra factor.
}
public static void main(String[] args) {
System.out.println(myPow(2.0, -2)); // 0.25
}
}The default invocation returns 0.25. myPow(-1.0, Integer.MIN_VALUE) returns 1 without overflowing the exponent. Java floating-point arithmetic is approximate; compare ordinary decimal examples with a tolerance, not exact decimal equality.
Call chain and dry run

Read the text transcript
Follow the Java, step by step
Example: x = 2.0, n = -2
What to track: Track the normalized base and each helper frame’s exponent. The multiplication happens while calls return, not while descending.
-
Normalize the negative exponent
Java operationx = 1.0 / x;Statex = 0.5; exponent is widened to long, then negated to 2The reciprocal turns the problem into a nonnegative power. Widening first also handles Integer.MIN_VALUE safely.
-
Descend once per frame
Java operationdouble half = positivePower(x, n / 2);Stateactive calls: positivePower(0.5,2) → positivePower(0.5,1) → positivePower(0.5,0)The two non-base frames wait for their single child; half is not available yet.
-
Return the multiplication identity
Java operationif (n == 0) return 1.0;Statethe n = 0 call returns 1.0 to the n = 1 frameA power of zero contains no factors, so the identity is 1, not 0.
-
Resume the odd exponent
Java operationreturn n % 2 == 0 ? square : square * x;Staten = 1; half = 1; square = 1; return 1 × 0.5 = 0.5An odd exponent needs one extra base after squaring the half-power.
-
Resume the even exponent
Java operationdouble square = half * half;Staten = 2; half = 0.5; square = 0.25; return 0.25Two equal half-powers already supply both factors. No extra multiplication by x is needed.
Final result: 0.25
positivePower(2,10)
→ positivePower(2,5)
→ positivePower(2,2)
→ positivePower(2,1)
→ positivePower(2,0) returns 1
n=1: 1×1×2 = 2
n=2: 2×2 = 4
n=5: 4×4×2 = 32
n=10: 32×32 = 1024The waiting calls retain their own n. Returning from n=0 does not make every caller’s n zero. Each caller combines the child’s answer according to its own even/odd case.
Why it works
The base case returns the multiplication identity. Assuming the child correctly returns x^floor(n/2), squaring gives the power with twice that exponent. The odd case contributes the missing final factor. Converting (x,-k) into (1/x,k) preserves the mathematical answer.
Complexity and alternative approaches
For exponent magnitude E, time and recursive auxiliary space are O(log(E+1)). Zero takes constant time. Only one recursive child is evaluated per level.
Repeated multiplication costs O(E), which is unusable for very large exponents. Iterative binary exponentiation performs the same squaring decisions with O(1) extra space and avoids recursive calls. Math.pow is useful in application code but does not demonstrate the requested algorithm.
Reciprocal-first evaluation avoids creating a huge positive power merely to invert it, though double overflow/underflow and rounding still follow floating-point limits.
Common mistakes
long exponent = -nstill negates n as an int. Widen first.- Taking the absolute value of
Integer.MIN_VALUEin int is also unsafe. - Forgetting the extra x for odd n produces the wrong power.
- Returning zero for exponent zero breaks the multiplicative identity.
- Forcing six-decimal output inside a method that must return double changes its return contract.