Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediummath-number-theory

Pow(x, n)

Problem (restated)

Implement pow(x, n): raise a floating-point x to the integer power n (which may be negative, including INT_MIN).

Intuition

Multiplying x n times is linear. Binary exponentiation squares the base and halves the exponent: x^13 = x^8 · x^4 · x^1. Negative n is 1 / x^|n|. Never negate INT_MIN as a 32-bit int.

Approaches

Binary exponentiation

Unverified

Time O(log |n|)Space O(1)

Idea. If n < 0, invert x and take |n| as a 64-bit exponent. While the exponent is live: if the low bit is set, multiply into the answer; square x; halve the exponent.

Walkthrough. 2^10: 2→4→16→32→1024 after the bits of 10 (1010) pick 2 and 8. 2^-2 inverts first → 0.25.

Trade-offs. The template. Use a long exponent so n = -2^31 does not overflow. In JS, do not use >> on the exponent (32-bit signed); divide instead.

Solution

export function myPow(x: number, n: number): number {
  let e = Math.abs(n);
  if (n < 0) x = 1 / x;
  let ans = 1;
  while (e > 0) {
    if (e % 2 === 1) ans *= x;
    x *= x;
    e = Math.floor(e / 2);
  }
  return ans;
}

export function myPow(x: number, n: number): number {
  let e = Math.abs(n);
  if (n < 0) x = 1 / x;
  let ans = 1;
  while (e > 0) {
    if (e % 2 === 1) ans *= x;
    x *= x;
    e = Math.floor(e / 2);
  }
  return ans;
}

Recursive square-and-multiply

Unverified

Time O(log |n|)Space O(log |n|) stack

Idea. pow(x, 0) = 1. half = pow(x, ⌊e/2⌋); even → half², odd → half² · x. Negative n wraps as 1 / pow(x, |n|).

Walkthrough. Same 2^10: five stack frames, each squares. Result 1024.

Trade-offs. The recurrence is the proof. Stack is log-depth. Interviews usually want the iterative loop.

Solution

export function myPow(x: number, n: number): number {
  const pow = (base: number, e: number): number => {
    if (e === 0) return 1;
    const half = pow(base, Math.floor(e / 2));
    const sq = half * half;
    return e % 2 === 0 ? sq : sq * base;
  };
  return n < 0 ? 1 / pow(x, -n) : pow(x, n);
}

export function myPow(x: number, n: number): number {
  const pow = (base: number, e: number): number => {
    if (e === 0) return 1;
    const half = pow(base, Math.floor(e / 2));
    const sq = half * half;
    return e % 2 === 0 ? sq : sq * base;
  };
  return n < 0 ? 1 / pow(x, -n) : pow(x, n);
}

Template connection

Modular-exponent shape of Math & Number Theory, without a modulus: square-and-multiply is the same loop as modPow. LC 372 adds % 1337 and a digit array.

Reflection

Walk the bits of the exponent. Square the base each step, and multiply into the answer when the bit is 1. The multiplications are O(log n).
A negative exponent is the reciprocal of the positive power. Negating the minimum int overflows; keep the exponent wide, or divide before negating.
Exponent 0 answers 1. Base 0 with a negative exponent divides by zero.