Pow(x, n)
Problem
myPow(x, n) that returns the double x
raised to the integer power n. The exponent can be negative
(meaning 1 / x|n|) and can be as extreme as
Integer.MIN_VALUE, so a loop of n multiplications is not an
option.x = 2.0, n = 10Output1024.0x = 1.5, n = 3Output3.375x = 4.0, n = -2Output0.0625-100.0 < x < 100.0 · -231 ≤ n ≤ 231-1 · x ≠ 0 or n > 0 · -104 ≤ xn ≤ 104
Try it yourself
class Solution {
public double myPow(double x, int n) {
}
}
xn = (xn/2)2 (times one extra
x when n is odd). Halving the exponent every step means only
about 31 squarings are ever needed, even for n = 231-1.Instinct If the answer for n items can be built from the same problem on halves (or smaller pieces) plus a cheap combine step - split, recurse, merge.
Memory hack Split it, trust it, stitch it - nail the base case, take the leap of faith on smaller calls, then glue their answers together.
Open the Recursion & Divide and Conquer guide →Approaches
Brute ForceRepeated Multiplication
O(|n|)Space O(1)Multiply an accumulator by x exactly |n| times, then
take the reciprocal if n was negative. Widening n to
long first makes |Integer.MIN_VALUE| representable.
public double myPow(double x, int n) { long e = Math.abs((long) n); // long: |MIN_VALUE| overflows int double result = 1.0; for (long i = 0; i < e; i++) { result *= x; } return n < 0 ? 1.0 / result : result; }
Correct, but ~2·109 multiplications for extreme n — times out.
BetterRecursive Fast Power (Halve the Exponent)
O(log |n|)Space O(log |n|)Compute half = xe/2 once, square it, and multiply by
one more x if e is odd. Each call halves the exponent, so
the recursion is only ≈31 levels deep. A negative exponent is handled up
front by switching to 1/x.
public double myPow(double x, int n) { long e = n; // widen before negating if (e < 0) { x = 1.0 / x; e = -e; } return power(x, e); } private double power(double x, long e) { if (e == 0) return 1.0; double half = power(x, e / 2); // reuse the half result, don't recompute it return (e % 2 == 0) ? half * half : half * half * x; }
Logarithmic time; costs a small O(log n) recursion stack.
OptimalIterative Binary Exponentiation
O(log |n|)Space O(1)Read the exponent in binary: x13 = x8 ·
x4 · x1 because 13 = 11012. Keep
squaring a running base (x, x2, x4, …)
and multiply it into the answer whenever the current low bit is 1.
public double myPow(double x, int n) { long e = n; // long so -(-2^31) fits if (e < 0) { x = 1.0 / x; e = -e; } double result = 1.0; double base = x; // x^(2^k) for the current bit k while (e > 0) { if ((e & 1) == 1) result *= base; base *= base; e >>= 1; } return result; }
Dry runx = 2.0, n = 10
- starte=10b=2r=110 = 1010 in binary
- bit 0e=5b=4r=1bit 0 → square only
- bit 1e=2b=16r=4bit 1 → r *= 4
- bit 0e=1b=256r=4bit 0 → square only
- bit 1e=0b=65536r=1024r *= 256 → 1024 ✔
Same O(log n) multiplications with constant space and no recursion.
long: -n for
n = -231 silently stays negative in int.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Repeated Multiplication | O(|n|) | O(1) |
| Better | Recursive Fast Power (Halve the Exponent) | O(log |n|) | O(log |n|) |
| Optimal | Iterative Binary Exponentiation | O(log |n|) | O(1) |
- Negating
nas anint—-Integer.MIN_VALUEis still negative. - Calling
power(x, e/2)twice per level — that silently becomes O(n). - Forgetting the reciprocal for negative exponents, or taking it after overflow to infinity.
- Start from the O(n) loop, then ask: “can I reuse xn/2?”
- Mention the
Integer.MIN_VALUEedge case before the interviewer does. - Note the same trick powers modular exponentiation and matrix power (Fibonacci in O(log n)).