#50 Pow(x, n)
frequently reported atMetaLinkedInBloombergMicrosoftGoogleAmazon
the problem
In plain words
Implement pow(x, n): x raised to the integer power n. n can be negative and as large as a 32-bit int.
in x = 2.00000, n = 10
out 1024.00000
in x = 2.10000, n = 3
out 9.26100
in x = 2.00000, n = -2
out 0.25000
2⁻² = 1/2² = 1/4.
- −100.0 < x < 100.0
- −2³¹ ≤ n ≤ 2³¹ − 1
- Either x ≠ 0 or n > 0
- −10⁴ ≤ xⁿ ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternDivide and conquer
xⁿ = (x^(n/2))² — and one more × x if n is odd. Computing x^(n/2) once halves the work every call: O(log n).
solutions
From brute force to optimal
Loop |n| times multiplying by x; invert at the end if n < 0.
- times = |n| as a long.
- result *= x, times times.
- If n < 0, return 1 / result.
Up to 2³¹ multiplications — Time Limit Exceeded on LeetCode.
One accumulator.
class Solution { public double myPow(double x, int n) { long times = Math.abs((long) n); // long: Math.abs(Integer.MIN_VALUE) overflows int double result = 1.0; for (long i = 0; i < times; i++) result *= x; return n < 0 ? 1.0 / result : result; }}half = pow(x, n/2); return half × half (× x if n is odd).
- Widen n to long N; if negative, x = 1/x, N = −N.
- Base case: N == 0 → 1.
- half = pow(x, N / 2) — one call.
- Even: half². Odd: half² × x.
N halves every call: at most about 33 calls, even for |n| = 2³¹.
One stack frame per halving.
class Solution { public double myPow(double x, int n) { long N = n; // -(-2³¹) does not fit in an int if (N < 0) { x = 1 / x; // x⁻ⁿ = (1/x)ⁿ N = -N; } return pow(x, N); } private double pow(double x, long n) { if (n == 0) return 1.0; // x⁰ = 1 double half = pow(x, n / 2); // ONE call, reused twice if (n % 2 == 0) return half * half; // even: xⁿ = (x^(n/2))² return half * half * x; // odd: one extra x }}Dry run
Read N's bits from low to high; square x each step and multiply it in when the bit is 1.
- Handle the sign like before.
- While N > 0: if the lowest bit is 1, result = x; x = x; N >>= 1.
One loop step per bit of N (≤ 32).
No recursion.
class Solution { public double myPow(double x, int n) { long N = n; if (N < 0) { x = 1 / x; N = -N; } double result = 1.0; while (N > 0) { if ((N & 1) == 1) result *= x; // this bit of N is set → include x^(2^i) x *= x; // x, x², x⁴, x⁸, … N >>= 1; } return result; }}in the room
How to say it in the interview
talk track
- Start with xⁿ = (x^(n/2))². Ask: what if n is odd? What if n is negative?
- Call out the
Integer.MIN_VALUEtrap before the interviewer does: −(−2³¹) doesn't fit in an int, so use along. - Stress that
pow(x, n/2)is computed once and stored — calling it twice is back to O(n).
traps
return pow(x, n/2) * pow(x, n/2)— two calls per level → O(n) again.n = -nwith n = −2³¹ stays negative → infinite recursion or wrong answer.- Comparing doubles with
==in your own tests — use a small tolerance.
what they ask next
Follow-ups
Modular power (aⁿ mod m) for huge n?
Same algorithm with long and % m after every multiplication — the backbone of RSA and many hashing tricks (LC 372 Super Pow).
Fibonacci in O(log n)?
Raise the matrix [[1,1],[1,0]] to the n-th power with exactly this halving trick.
before you submit
Edge cases to test
- n = 0 → 1.0 for any x.
- n = Integer.MIN_VALUE: −n doesn't fit in an int — widen to long first.
- Negative x with an odd n gives a negative answer: (−2)³ = −8.
practise next
Similar problems
- #69Sqrt(x)Easyin Big-O
- #191Number of 1 BitsEasyin Bits