Pow in TypeScript: Halve the Exponent, Mind the Number

Multiplying a number by itself a few times is easy. Doing it more than two billion times is a less appealing afternoon. Pow(x, n) asks us to recognise that the exponent describes repeated structure we can reuse, rather than a loop we must dutifully finish.
The main idea is exponentiation by squaring. The JavaScript‑specific trap is trying to express that idea with bitwise operators copied from a language whose integer model is different. A clever‑looking shift can turn a perfectly valid positive exponent into a negative one.
In LeetCode's Pow(x, n) problem, the exponent is an integer within the signed 32‑bit range. The base is a floating‑point number, and negative exponents are allowed. I'll keep the arithmetic explicit so that those limits remain visible.
Repeated Squaring Reuses Completed Work
For an even exponent, x^n = (x × x)^(n / 2). We can square the base and halve the exponent without changing the value we're trying to obtain. For an odd exponent, we first retain one copy of the base, then apply the same reduction to the remaining even part.
An iterative implementation keeps three values: the result already accumulated, the current factor, and the exponent still to be processed. When that exponent is odd, we multiply the result by the current factor. We then halve the exponent, discarding the remainder, and square the factor for the next step.
Take 3^5. Initially the result is one, the factor is three, and the remaining exponent is five. Five is odd, so the result becomes three. We halve the exponent to two and square the factor to nine.
Two is even, so the result stays three. Halving gives one, and squaring gives 81. One is odd, so multiplying the result by 81 gives 243. The remaining exponent becomes zero, and we're done.
We used the factors corresponding to the set bits of five, but we didn't need to coerce the exponent into a bitwise representation to do it. Remainder and integer division are enough.
The Invariant Explains the Loop
Ignoring floating‑point rounding for the moment, result × factor^remaining stays equal to the requested power throughout the loop. That expression is useful because it describes both odd and even iterations in one place.
For an odd remaining exponent, moving one factor into the result leaves an even number of factors. Squaring the factor and halving that even count preserves the product. For an even exponent, we can apply the squaring step directly.
When the remaining exponent reaches zero, its factor contributes one, so the accumulated result is the requested value. Initialising the result to one is therefore the multiplicative equivalent of an empty sum starting at zero.
The implementation skips the final unnecessary square once the exponent has reached zero. That doesn't alter the invariant or the answer; it simply avoids computing a value we'll never read, which could also overflow for some inputs outside the problem's useful range.
Handle the Sign Before the Loop
A negative exponent means taking a reciprocal: x^(-k) = (1 / x)^k. We can invert the base once, take the exponent's magnitude, and run the same positive‑exponent loop.
This also avoids computing a potentially enormous positive power first and only then taking its reciprocal. For negative exponents and a base larger than one in magnitude, inverting first works towards the small result directly.
The minimum allowed exponent is -2^31. Its positive magnitude, 2^31, does not fit a signed 32‑bit integer, but it does fit exactly in a JavaScript number. Math.abs(n) is therefore safe for this problem.
The trouble starts if we then use signed right shifts. JavaScript number bitwise operations use 32‑bit conversions; 2^31 becomes negative under a signed interpretation. The ECMAScript right‑shift definition is the relevant rule, rather than the type annotation saying number.
I use Math.floor(remaining / 2) and remaining % 2 so the exponent remains an ordinary non‑negative integer throughout. This is slightly less cryptic and avoids importing an unnecessary representation limit.
Complete TypeScript Implementation
const myPow = (x: number, n: number): number => {
let factor = n < 0 ? 1 / x : x;
let remaining = Math.abs(n);
let result = 1;
while (remaining > 0) {
if (remaining % 2 === 1) result *= factor;
remaining = Math.floor(remaining / 2);
if (remaining > 0) factor *= factor;
}
return result;
};Each iteration halves the remaining exponent, giving O(log(|n| + 1)) running time and O(1) additional storage. The largest allowed magnitude needs only 32 iterations. That's the useful improvement over repeated multiplication; I wouldn't attach a universal timing claim to it without measuring an actual runtime and workload.
For exponent zero, the loop doesn't run and the function returns one. The problem excludes zero raised to zero and zero with a negative exponent, so we don't need to define additional behaviour for those cases. Zero with a positive exponent works normally.
A negative base also works. Odd exponents preserve a negative result and even exponents produce a positive result. Squaring the factor naturally handles that parity after the first odd contribution.
Floating‑Point Arithmetic Still Has a Say
Exponentiation by squaring changes the order of multiplications. Floating‑point multiplication isn't perfectly associative, so its result need not match repeated multiplication or the built‑in power operator bit‑for‑bit.
That's not a licence to ignore substantial differences. It means the comparison needs a tolerance appropriate to the expected magnitude and the problem's requirements. A typical comparison uses an absolute tolerance for values near zero and a relative tolerance for larger values.
I would test integer powers with exactly representable results, such as powers of two within a sensible range, using exact equality. For fractional bases, compare against an independent reference with a justified tolerance and print both values on failure.
Large exponents with bases very close to one deserve explicit tests. Repeated squaring can amplify small rounding errors through many mathematical powers even though the loop itself is short. This educational function isn't a claim to reproduce every edge case or accuracy guarantee of a platform maths library.
For ordinary application code, use the built‑in exponentiation operator or Math.pow unless you have a specific reason to implement the algorithm. The exercise teaches decomposition; it doesn't oblige us to maintain a replacement maths library as a hobby.
Cases Worth Keeping
Test exponents zero, one, minus one, the minimum signed 32‑bit value, and the maximum value. Bases one and minus one make the extreme exponents easy to verify without creating huge results. Add a zero base with a positive exponent, a fractional base, and negative bases with both parities.
For modest integer exponents, a reference that multiplies repeatedly is independent of the halving logic. For wider cases, compare with the built‑in operator using a stated tolerance. A check that negating an exponent approximately reciprocates the answer is also useful when neither side overflows or underflows.
My binary‑search walkthrough uses a different halving process, but shares the discipline of stating what remains unresolved after each iteration. My dynamic‑programming state guide asks a related question about which completed work is worth retaining.
Wrapping Up
The speed comes from preserving a product whilst repeatedly halving its exponent. Handling the sign once keeps the loop simple, and ordinary arithmetic avoids the signed 32‑bit trap.
I'd keep those two arguments separate from floating‑point accuracy. One explains why the algorithm computes the right mathematical power; the other explains how closely a particular numeric representation can carry it out.