The naive approach is simply running a loop n times, multiplying result by x in each iteration (and if n is negative, doing 1/x). While correct mathematically, this is an O(n) solution. If n = 2^{31}-1 (over 2 billion), this loop will take several seconds and result in a Time Limit Exceeded (TLE) error. We need something much faster.
x^{-n} = 1 / x^n, so the obvious move is to negate n and invert at the end.
But negating the most negative 32-bit integer overflows. The range is -2^{31} to 2^{31}-1, so -(-2^{31}) does not fit.
In Python integers are unbounded and this cannot happen. In Java, C++ or C it can, and the standard fix is to widen n to a 64-bit type before negating.
Mention it. It is exactly the kind of detail that separates someone who has thought about the range from someone who has not, and this problem's constraints are worded to invite the question.
class Solution: def myPow(self, x: float, n: int) -> float: if n < 0: # (1) x = 1 / x # (2) n = -n result = 1.0 # (3) while n: # (4) if n & 1: # (5) this bit of the exponent is set result *= x x *= x # (6) x, x², x⁴, x⁸, … n >>= 1 # (7) move to the next bit return result # (8)
ts
function myPow(x: number, n: number): number { if (n < 0) { // (1) x = 1 / x; // (2) n = -n; } let result = 1; // (3) while (n > 0) { // (4) if (n % 2 === 1) result *= x; // (5) x *= x; // (6) n = Math.floor(n / 2); // (7) } return result; // (8)}
This is fast exponentiation, also called exponentiation by squaring. It uses the fact that any whole-number power can be built from the powers x^1, x^2, x^4, x^8, \dots, one for each 1 in the exponent written in binary. For example, 13 is 1101 in binary, which is 8 + 4 + 1, so x^{13} = x^8 \times x^4 \times x^1.
(1) A negative power means "one over".x^{-n} = \frac{1}{x^n}.
(2) So flip x to 1 / x, and make n positive.
(3) The answer starts at 1, because multiplying by 1 changes nothing.
(4) Keep going while some bits of n are left.
(5) Is the lowest bit of n a 1?n & 1 keeps only the last binary digit. If it is 1, this power of x is part of the answer, so multiply it in. TypeScript checks the same thing with n % 2 === 1.
(6) Square x, so it moves on to the next power in the list: x, then x^2, then x^4, then x^8.
(7) Drop the lowest bit of n.n >>= 1 shifts every bit one place to the right, which is the same as halving and rounding down.
(8) The product of the powers whose bits were 1.
n & 1 tests the lowest bit — whether n is odd. n >>= 1 divides by two, discarding that bit. Together they walk the exponent's binary representation from the least significant end.
x *= x on every iteration, whether or not the bit was set, because the next bit represents twice the exponent.
Code Walkthrough:
Handling Negative Exponents: If n is negative, we invert x (x = 1/x) and make n positive. This turns x^{-n} into (1/x)^n.
Initialization: We set result = 1.0.
Iteration (while n): We loop as long as n > 0.
Applying Bits (if n & 1): We check if the lowest bit of n is 1 (i.e., n is odd). If it is, we multiply our result by the current weight of x.
Squaring the Base (x *= x): Regardless of the bit, we square x. This prepares x for the next bit position (e.g., passing from x^1 to x^2 to x^4).
Shifting the Exponent (n >>= 1): We shift n right by 1 bit, moving to the next most significant bit in the exponent.
result starts at 1, which is what makes n = 0 return 1 with no special case.
In JavaScript use Math.floor(n / 2) rather than n >>= 1 — the bitwise operators coerce to 32-bit signed integers, which would break for large n.
def myPow(self, x, n): if n < 0: return 1 / self.myPow(x, -n) if n == 0: return 1.0 half = self.myPow(x, n // 2) return half * half if n % 2 == 0 else half * half * x
half must be computed once and reused. Writing myPow(x, n//2) * myPow(x, n//2) makes two recursive calls instead of one, and the whole thing collapses back to O(n). That is the classic mistake here, and it is the same "compute once, use twice" discipline as memoisation.
O(\log n) stack depth, which is fine at 32 levels.
Repeated multiplication accumulates rounding error. pow(2.0, 10) is exact because powers of two are exact in binary, but pow(2.1, 3) will be very slightly off from 9.261 — LeetCode accepts a small tolerance for this reason.
For integer bases with a modulus, the identical algorithm with % m after each multiplication is modular exponentiation, and it is the operation RSA is built on. Chapter 8 covers that, and mentioning it here shows the algorithm is not a puzzle.
Time Complexity:O(\log n). In each step, we divide the exponent n by 2 (right shift). The number of times we can halve n before it reaches 0 is exactly bounded by the number of bits in n, which is \log_2(n) (at most 32 operations).
Space Complexity:O(1). The iterative version uses only a few variables (result, x, n) and requires no call stack. (The recursive version takes O(\log n) space due to the recursion stack).
Modular exponentiation — the same loop with % m, and the core of RSA and Diffie-Hellman.
Matrix exponentiation — replace the multiplication with matrix multiplication and you can compute the n-th Fibonacci number in O(\log n). A neat connection back to 4.23.1.
Super Pow (LeetCode 372) — the exponent itself is an array of digits.
Sqrt(x) — binary search on the answer instead. 4.11.
"Why is it O(\log n)?" The exponent halves every iteration.
"What goes wrong with negative n?" Negating the most negative integer overflows in fixed-width languages.
"Why does the recursive version need half in a variable?" Two recursive calls would make it O(n).
"What about floating-point error?" It accumulates; exact answers need integer or rational arithmetic.
"What if you needed the result modulo something?" Apply % m after each multiplication — that is modular exponentiation, and it is what public-key cryptography runs on.
One thing to volunteer: explain the algorithm in terms of the exponent's binary digits. "13 is 1101, so I need x^8 \cdot x^4 \cdot x^1." It makes the loop obviously correct instead of a trick.
Next:4.28.7 Multiply Strings — long multiplication, and the index formula that makes it work.