Math for interviews

What these problems have in common

A math problem in an interview is usually not hard mathematics. It is a small fact about integers that, once you know it, replaces a loop over a huge range with a loop over a handful of steps. "Is this number prime?" looks like n divisions and costs about the square root of n. "How many trailing zeros does 1000000! have?" looks impossible and takes eight divisions. "Return the answer modulo 1000000007" tells you the true answer has thousands of digits and that you must never build it.

The chapter walks through the facts that come up again and again, in the order each one is needed to build the next: how JavaScript stores numbers, gcd, primes, modular arithmetic, fast exponentiation, the modular inverse, binomial coefficients, Pascal's triangle, Catalan numbers, matrix exponentiation, Josephus, number formatting, digit problems, happy and ugly numbers, and the counting side of probability. For each one the order is the same: the shape of the problem, the idea derived from small cases, the complete JavaScript, a trace by hand, the cost, and the mistakes that lose offers.

The input limits tell you which tool to reach for. Read them before you read the story.

Numbers in JavaScript: where exactness ends

Every JavaScript Number is a 64-bit floating-point value. It has 53 bits for the digits, which means every integer from -(2⁵³ - 1) to 2⁵³ - 1 is stored exactly, and beyond that the gaps open up. Between 2⁵³ and 2⁵⁴ the representable integers are the even ones only, so the odd ones round to a neighbour. This is not a rare edge case in this chapter. A product of two numbers below 10⁹ is about 10¹⁸, far past the limit, and the result is silently wrong, not an error.

Number.MAX_SAFE_INTEGER;            // 9007199254740991, which is 2 ** 53 - 1
2 ** 53 + 1 === 2 ** 53;            // true: the +1 is lost
Number.isSafeInteger(2 ** 53);      // false
999999999 * 999999998;              // 999999997000000000, but written out exactly the product is 999999997000000002
(999999999n * 999999998n);          // 999999997000000002n: BigInt keeps every digit

BigInt is the built-in type for integers of any size. It is the right tool for the few multiplications that leave the safe range, and these rules are worth knowing before you use it in an interview:

• You write a BigInt literal with a trailing n, or convert with BigInt(value). BigInt(1.5) throws a RangeError; only integers convert.
• You cannot mix the two types in arithmetic: 1n + 1 throws a TypeError. Convert one side explicitly.
• Math.sqrt, Math.max and the other Math functions reject BigInt. JSON.stringify throws on it too.
• Division truncates toward zero and % takes the sign of the dividend, just as for Numbers: -7n / 2n is -3n and -7n % 3n is -1n.
• Comparison across types works (1n < 2 is true, 1n == 1 is true) but 1n === 1 is false, because the types differ.
• Converting back with Number(big) rounds silently when the value is past 2⁵³. Convert back only when the value is known to be small, such as a residue below the modulus.

Two more details bite in integer code. The remainder operator keeps the sign of the left side, so -7 % 3 is -1, not 2. A residue that should be in [0, m) needs a helper. And the bitwise operators (|, &, <<, >>) first convert the number to a signed 32-bit integer, so they are fine for values below 2³¹ and wrong above it.

function mod(a, m) {
  return ((a % m) + m) % m; // the result is always in [0, m), even for negative a
}

mod(-7, 3);          // 2
-7 % 3;              // -1
2147483648 >> 1;    // -1073741824: the shift sees the 32-bit pattern of a negative number
2147483648 >>> 1;   // 1073741824: unsigned shift reads it as 2^31 and is correct here

The modular multiplication problem, and two fixes

Most "modulo 10⁹ + 7" problems multiply two residues that are each just below 10⁹ + 7. The product is near 10¹⁸, past 2⁵³, so the plain expression (a * b) % m has already lost its low digits before the % runs. The plain version fails quietly, which is the dangerous part.

function naiveMulMod(a, b, m) {
  return (a * b) % m;
}

function mulMod(a, b, m) {
  return Number((BigInt(a) * BigInt(b)) % BigInt(m)); // exact: BigInt holds the whole product
}

naiveMulMod(999999999, 999999998, 1000000007); // 70, wrong
mulMod(999999999, 999999998, 1000000007);      // 72, correct: (-8) * (-9) mod p

The result of mulMod is a residue below m, so converting it back to a Number is safe. When the modulus is small enough that every product of two residues fits in 2⁵³, which is the case for m - 1 <= 94906265 (about 9.4 * 10⁷), plain (a * b) % m is exact and BigInt is not needed. Multiplying a residue by a small loop counter is also safe: fact * i stays below 2⁵³ for every i up to about nine million when the modulus is 10⁹ + 7, which is why a factorial table filled with a plain Number loop is correct, while a product of two residues is not.

If you do not want BigInt, the second fix is to build the product by doubling and adding, the same halving idea as fast exponentiation below. Every intermediate value stays below twice the modulus, so it works for any modulus up to 2⁵² using only Numbers, at O(log b) per multiplication.

function mulModNoBigInt(a, b, m) {
  let result = 0;
  a %= m;
  while (b > 0) {
    if (b % 2 === 1) result = (result + a) % m; // add the current doubling of a when this bit of b is set
    a = (a * 2) % m;                            // a, 2a, 4a, ... each reduced mod m
    b = Math.floor(b / 2);
  }
  return result;
}

gcd and lcm: Euclid on remainders

The greatest common divisor of a and b is the largest integer that divides both. Listing divisors costs O(min(a, b)). Euclid's observation is that the divisors of the pair (a, b) are exactly the divisors of the pair (b, a mod b). To see why, write a = q * b + r with r = a mod b. A number d that divides b and a divides q * b and therefore divides a - q * b = r. A number d that divides b and r divides q * b + r = a. Both pairs have the same common divisors, so they have the same greatest one: gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a stops the recursion.

function gcd(a, b) {
  a = Math.abs(a);
  b = Math.abs(b);
  while (b !== 0) {
    const r = a % b;
    a = b;
    b = r;
  }
  return a;
}

function lcm(a, b) {
  if (a === 0 || b === 0) return 0;
  return (Math.abs(a) / gcd(a, b)) * Math.abs(b); // divide first, then multiply, so the intermediate stays small
}

gcd(252, 105); // 21
lcm(4, 6);     // 12

Dry run: gcd(252, 105)

Cost. It takes O(log(min(a, b))) steps. The reason: for a at least b, a mod b is less than a / 2. If b is at most a / 2, then a mod b is less than b, so it is below a / 2. If b is more than a / 2, then a mod b = a - b, which is also below a / 2. One step turns (a, b) into (b, r) with r below a / 2, and the next step turns that into (r, r2), so after every two steps the larger number of the pair is less than half of what it was. After the first step the pair is bounded by min(a, b), which gives the logarithm of the smaller input. The slowest inputs are pairs of consecutive Fibonacci numbers (Lamé's theorem, quoted here and not proved).

lcm and overflow. The identity is gcd(a, b) * lcm(a, b) = a * b, and you divide first because a * b may leave the safe range even when the lcm itself does not. The lcm of 1000000007 and 998244353 is their product, and as a Number it comes out as 998244359987710500 while the true value is 998244359987710471. When the answer can pass 2⁵³, switch to BigInt.

function gcdBig(a, b) {
  while (b !== 0n) [a, b] = [b, a % b];
  return a;
}

function lcmBig(a, b) {
  return (a / gcdBig(a, b)) * b;
}

lcmBig(1000000007n, 998244353n); // 998244359987710471n

The lcm of a whole array is a fold: lcm = lcm(lcm(a0, a1), a2), and the gcd of an array folds the same way. Two other uses show up often. Reducing a fraction divides numerator and denominator by their gcd. Hashing a direction, such as the slope between two points, divides both differences by their gcd so that (2, 4) and (1, 2) become the same key.

Extended Euclid: finding x and y with a * x + b * y = gcd(a, b)

Running the same recursion backward produces the coefficients. Suppose the recursive call on (b, a mod b) returned x' and y' with b * x' + (a mod b) * y' = g. Since a mod b = a - floor(a / b) * b, that says a * y' + b * (x' - floor(a / b) * y') = g, so the pair for (a, b) is x = y' and y = x' - floor(a / b) * y'. The base case (a, 0) gives x = 1, y = 0.

function extendedGcd(a, b) {
  if (b === 0) return { g: a, x: 1, y: 0 };
  const { g, x, y } = extendedGcd(b, a % b);
  return { g, x: y, y: x - Math.floor(a / b) * y };
}

extendedGcd(240, 46); // { g: 2, x: -9, y: 47 }, since 240 * (-9) + 46 * 47 = 2

Read the table from the bottom up: each row computes its pair from the row below it. The recursion depth is the number of Euclid steps, which is logarithmic, so the stack is not a concern.

The Bézout identity this gives (a * x + b * y = gcd) has an interview use that is easy to forget. In "Water and Jug", you can measure exactly z litres with jugs of capacity x and y if and only if z is at most x + y and z is a multiple of gcd(x, y), because the amounts reachable by fills, empties and pours are exactly the integer combinations of x and y.

function canMeasureWater(x, y, z) {
  if (z === 0) return true;
  return z <= x + y && z % gcd(x, y) === 0;
}

Primes: trial division and the sieve

Is n prime? If n = a * b with 1 < a <= b, then a * a <= a * b = n, so the smaller factor is at most the square root of n. If n has any divisor besides 1 and itself, it has one in [2, sqrt(n)], and testing those divisors is enough. Write the bound as d * d <= n and not d <= Math.sqrt(n): the multiplication is an exact integer comparison, and it avoids calling a floating-point function in the loop.

function isPrime(n) {
  if (n < 2) return false; // 0, 1 and negatives are not prime
  for (let d = 2; d * d <= n; d++) {
    if (n % d === 0) return false;
  }
  return true;
}

function primeFactors(n) {
  const factors = new Map(); // prime -> exponent
  for (let d = 2; d * d <= n; d++) {
    while (n % d === 0) {
      factors.set(d, (factors.get(d) ?? 0) + 1);
      n /= d; // exact division, since d divides n
    }
  }
  if (n > 1) factors.set(n, (factors.get(n) ?? 0) + 1); // what is left over is itself a prime
  return factors;
}

primeFactors(360); // Map { 2 => 3, 3 => 2, 5 => 1 }

primeFactors never has to test whether d is prime. By the time the loop reaches a composite d, every prime factor of d has already been divided out of n completely, so d cannot divide what remains. The leftover after the loop is 1 or a single prime above the square root: a leftover with two prime factors would be at least (sqrt(n))², which contradicts the loop having run only up to the square root. Each call costs O(sqrt(n)) steps. That is fine for one number up to about 10¹², and too slow for a million queries.

The sieve of Eratosthenes

For many queries or for "count the primes below n", do the work once for all numbers. Walk upward from 2. The first number not yet crossed out is prime, and every multiple of it is composite, so cross those out. Whatever survives at the end is prime.

function sieve(n) {
  const composite = new Uint8Array(n + 1); // one byte per number, all 0 at the start
  const primes = [];
  for (let i = 2; i <= n; i++) {
    if (composite[i] === 1) continue;       // crossed by a smaller prime
    primes.push(i);
    for (let j = i * i; j <= n; j += i) composite[j] = 1; // start at i * i, not 2 * i
  }
  return primes;
}

function countPrimes(n) { // how many primes are strictly below n
  if (n < 3) return 0;
  const composite = new Uint8Array(n);
  let count = 0;
  for (let i = 2; i < n; i++) {
    if (composite[i] === 1) continue;
    count++;
    for (let j = i * i; j < n; j += i) composite[j] = 1;
  }
  return count;
}

sieve(30);       // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
countPrimes(10); // 4: the primes 2, 3, 5, 7

Why start at p * p. A multiple k * p with k < p has a prime factor smaller than p (any prime factor of k), so an earlier prime has already crossed it. The first multiple of p that nobody has crossed is p * p. It also means the inner loop runs only when p * p <= n, that is, for primes up to the square root of n, which is why the loop writes j = i * i and needs no separate bound.

Why O(n log log n). The outer loop visits n numbers. The inner loop for a prime p crosses at most n / p numbers, so the crossing work totals at most n * (1/2 + 1/3 + 1/5 + 1/7 + ...), summed over the primes up to the square root of n. If you sum 1/k over all integers up to n, you get about ln n, which would give n log n. The same sum over primes only grows like ln ln n, a classical result of Mertens that is quoted here and not proved. ln ln n is about 3 for n = 10⁹, so for any n you can allocate memory for, the sieve is a few steps per element. Space is one byte per number with a Uint8Array, so 10⁷ numbers take about 10 megabytes.

Dry run: the sieve on n = 30

The smallest-prime-factor table

A variation records, for every number, its smallest prime factor. With that table, factorizing any x up to n takes one step per prime factor (at most about log₂ x steps) instead of a trial division up to the square root. It is the better tool when the same program factorizes many numbers.

function smallestPrimeFactors(n) {
  const spf = new Uint32Array(n + 1); // 0 means "not set yet"
  for (let i = 2; i <= n; i++) {
    if (spf[i] !== 0) continue;        // already has a smaller prime factor
    for (let j = i; j <= n; j += i) {
      if (spf[j] === 0) spf[j] = i;    // first prime to reach j is its smallest
    }
  }
  return spf;
}

function factorizeWith(spf, x) {
  const primes = [];
  while (x > 1) {
    primes.push(spf[x]);
    x /= spf[x];
  }
  return primes;
}

factorizeWith(smallestPrimeFactors(100), 84); // [2, 2, 3, 7]

This version starts the inner loop at i, not at i * i, because it has to set the smallest factor of numbers such as 6 = 2 * 3. The total is still O(n log log n), since it sums n / p over all primes p up to n.

Modular arithmetic and the 1e9+7 constant

When a problem says "return the answer modulo 10⁹ + 7", it is telling you that the true value, for example the number of paths through a large grid, has more digits than any integer type can hold. The remainder is small, and the useful fact is that you can take the remainder at every step instead of at the end, because addition, subtraction and multiplication all respect it:

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a - b) mod m = ((a mod m) - (b mod m) + m) mod m
(a * b) mod m = ((a mod m) * (b mod m)) mod m

Division is the operation that does not carry over: a / b mod m is not the same as (a mod m) / (b mod m). It needs a modular inverse, which the section after fast exponentiation covers. 10⁹ + 7 is the usual modulus because it is a prime that fits in 30 bits, so every residue is below 2³⁰ and sums of two residues fit in an ordinary int in any language. That is a convention of the problem setters, not a law, and 998244353 is the other common one.

Fast exponentiation

Computing xⁿ by n multiplications is far too slow when n is 10⁹, and the numbers are huge before you reduce them. The idea is that the binary digits of n tell you which powers of x to multiply. Write n = 13 = 8 + 4 + 1, so x¹³ = x⁸ * x⁴ * x¹. The powers x¹, x², x⁴, x⁸ come from squaring the previous one. So the loop keeps a base that is squared each round and multiplies it into result on every round where the current bit of n is 1. The number of rounds is the number of bits in n, about log₂ n.

function powMod(base, exp, m) {
  const modulus = BigInt(m);
  let result = 1n % modulus;                                 // 1n % 1n is 0n, which makes m = 1 work
  let b = ((BigInt(base) % modulus) + modulus) % modulus;    // a negative base becomes its residue
  let e = BigInt(exp);                                       // pass a BigInt for exponents above 2^53
  while (e > 0n) {
    if (e & 1n) result = (result * b) % modulus;             // this bit of the exponent is set
    b = (b * b) % modulus;                                   // b is now x^(2^i) for the next bit
    e >>= 1n;
  }
  return Number(result);
}

powMod(2, 10, 1000000007);       // 1024
powMod(3, 13, 1000);             // 323, because 3^13 = 1594323
powMod(2, 1000000000000n, 1000000007);

Dry run: powMod(3, 13, 1000), with 13 = 1101 in binary

The four rounds used the powers 3¹, 3⁴ and 3⁸ of 3, and 3 * 81 * 6561 = 3¹³. Cost: O(log n) multiplications: for n near 10⁹ that is about 30 squarings and at most 30 products into the result. Space: O(1). The recursive form, xⁿ = (x^n/2)² times x when n is odd, is the same algorithm; the loop above is the one to write when the exponent is large, since it has no stack.

Exponents that arrive as digits. "Super Pow" gives the exponent as an array of decimal digits that is too long to hold as a number. Process the digits left to right and use a^{10q + d} = (a^q)¹⁰ * a^d: the exponent so far, q, becomes 10q + d when digit d is appended, so the result so far is raised to the tenth power and multiplied by a^d.

function superPow(a, digits) {
  const M = 1337;
  let result = 1;
  for (const d of digits) {
    result = (powMod(result, 10, M) * powMod(a, d, M)) % M; // both factors are below 1337, so the product is safe
  }
  return result;
}

superPow(2, [1, 0]); // 1024, since 2^10 = 1024

pow(x, n) with doubles: negative exponents and edge cases

The version everyone is asked for is pow(x, n) with x a decimal number and n a signed 32-bit integer. The loop is the one above, with plain multiplication and no modulus. The edge cases decide whether it passes.

function powFloat(x, n) {
  let e = Math.abs(n);              // no n >> 1 and no negating through a bitwise operator
  let base = n < 0 ? 1 / x : x;    // invert the base first, not the result
  let result = 1;
  while (e > 0) {
    if (e % 2 === 1) result *= base;
    base *= base;
    e = Math.floor(e / 2);
  }
  return result;
}

powFloat(2, 10);    // 1024
powFloat(2, -2);    // 0.25
powFloat(0, -1);    // Infinity, as Math.pow(0, -1) gives
powFloat(2, -1074); // 5e-324, the smallest positive Number

• The most negative exponent. In a language with 32-bit integers, -n for n = -2147483648 overflows back to itself. JavaScript Numbers are doubles, so Math.abs(-2147483648) is simply 2147483648. The trap is the bitwise shift: (-(-2147483648)) >> 1 is -1073741824, because the operator first reinterprets the value as a 32-bit signed integer. Halve with Math.floor(e / 2) or >>>.
• Parity of a negative exponent. -3 % 2 is -1, so the test e % 2 === 1 fails for negative e. Take the absolute value once before the loop, as above.
• Where to invert. If you compute x^|n| first and return 1 / result, then for x = 2 and n = -1074 the result 2¹⁰⁷⁴ overflows to Infinity and the answer becomes 0, though 2^-1074 is representable. Inverting the base first avoids it.
• No integer overflow, but Infinity and underflow. Doubles do not wrap. Results too large become Infinity, too small become 0, and 0 ** 0 is 1 by convention in both JavaScript and the usual problem statement.
• Accuracy. Repeated squaring performs about log n roundings, so the result is close to Math.pow but not always bit-identical. Compare with a relative tolerance, never with ===.

The same loop with integers and a modulus is powMod. Both are instances of one idea, which is why fast exponentiation also works for matrices (below) and for any associative operation.

Integer square root

For floor(sqrt(n)) the quick answer is Math.floor(Math.sqrt(n)), and for small n it is right. It is not right for every safe integer, because Math.sqrt rounds to the nearest double and the true root of k * k - 1 sits just under k. For n = 4503599761588224, which is 67108865 * 67108865 - 1, it returns 67108865, one too many. (In Node 24 it matched the exact answer at every perfect-square boundary up to 67108864 squared, and the first miss is the k above.) So correct the estimate with integer arithmetic. A binary search on r, looking for the largest r with r * r <= n, is the other standard method, and the exercise on integer square root practises it.

function integerSqrt(n) {
  let r = Math.floor(Math.sqrt(n));
  while (r * r > n) r--;               // the estimate was one too high
  while ((r + 1) * (r + 1) <= n) r++;   // the estimate was one too low
  return r;
}

integerSqrt(99);  // 9
integerSqrt(100); // 10

Modular inverse and nCr mod p

The inverse of a modulo m is the number x with a * x = 1 (mod m). It is what "divide by a" means in modular arithmetic: to compute (b / a) mod m, compute b times the inverse of a. It exists exactly when gcd(a, m) = 1, and there are two ways to find it.

Way 1, for any modulus: extended Euclid. If gcd(a, m) = 1 then extendedGcd returns x and y with a * x + m * y = 1, and reducing modulo m leaves a * x = 1, so x mod m is the inverse.

function modInverse(a, m) {
  const { g, x } = extendedGcd(mod(a, m), m);
  if (g !== 1) return null; // a and m share a factor, so no inverse exists
  return mod(x, m);
}

modInverse(3, 11);  // 4, since 3 * 4 = 12 = 1 (mod 11)
modInverse(4, 12);  // null

Way 2, for a prime modulus p: Fermat's little theorem. For a prime p and a not divisible by p, a^p-1 = 1 (mod p). The short proof: the numbers a, 2a, ..., (p-1)a are all different modulo p (two equal ones would give p dividing (i - j) * a) and none is 0, so they are the numbers 1 to p-1 in some order. Their product is therefore (p-1)! on both sides, giving a^p-1 * (p-1)! = (p-1)! (mod p), and since (p-1)! is coprime to p you may cancel it. Rewriting, a * a^p-2 = 1, so the inverse of a is a^p-2, which powMod(a, p - 2, p) computes in O(log p).

Binomials modulo a prime

The binomial coefficient C(n, r) = n! / (r! * (n - r)!) counts the ways to choose r of n items. It is huge, the problem wants it modulo p, and the formula contains a division. The standard recipe precomputes the factorials once, then the inverse factorials, then answers each query with two multiplications.

The inverse factorials come from one power and a backward loop. Compute invFact[limit] = fact[limit]^(p-2) once. Then because 1 / (i - 1)! = i / i!, each earlier value is invFact[i - 1] = invFact[i] * i. That avoids a modular power per entry.

function buildFactorials(limit, p) {
  const fact = new Array(limit + 1);
  const invFact = new Array(limit + 1);
  fact[0] = 1;
  for (let i = 1; i <= limit; i++) fact[i] = mulMod(fact[i - 1], i, p);
  invFact[limit] = powMod(fact[limit], p - 2, p);
  for (let i = limit; i >= 1; i--) invFact[i - 1] = mulMod(invFact[i], i, p);
  return { fact, invFact };
}

function nCrMod(n, r, tables, p) {
  if (r < 0 || r > n) return 0;
  const { fact, invFact } = tables;
  return mulMod(mulMod(fact[n], invFact[r], p), invFact[n - r], p);
}

const P = 1000000007;
const tables = buildFactorials(1000, P);
nCrMod(10, 3, tables, P); // 120

Dry run with a small prime: p = 13, limit = 5

invFact[5] is 3¹¹ mod 13 = 9, and 3 * 9 = 27 = 1 (mod 13), which confirms it. The row then fills right to left: invFact[4] = 9 * 5 = 45 = 6, invFact[3] = 6 * 4 = 24 = 11, invFact[2] = 11 * 3 = 33 = 7. To answer C(5, 2): fact[5] * invFact[2] * invFact[3] = 3 * 7 * 11 = 231, and 231 mod 13 is 10, which is C(5, 2).

Cost. O(limit) for the tables plus O(log p) once for the power, then O(1) per query. Without a modulus, the question is whether C(n, r) fits at all; the next section handles that.

Pascal's triangle and exact binomials

Without a modulus, or with a modulus that is not prime, binomials come from Pascal's rule, and it is the first thing to try for small n. Choosing r of n items either leaves out the last item, which is C(n - 1, r) ways, or includes it and then chooses r - 1 of the others, C(n - 1, r - 1) ways. So C(n, r) = C(n - 1, r - 1) + C(n - 1, r), with C(n, 0) = C(n, n) = 1. The table of these values is Pascal's triangle, and row n adds up to 2ⁿ.

function pascalRows(numRows) {
  const rows = [];
  for (let i = 0; i < numRows; i++) {
    const row = new Array(i + 1).fill(1);          // the two ends are 1
    for (let j = 1; j < i; j++) {
      row[j] = rows[i - 1][j - 1] + rows[i - 1][j]; // the two entries above
    }
    rows.push(row);
  }
  return rows;
}

function pascalRow(rowIndex) { // row n alone, in O(n) space
  const row = new Array(rowIndex + 1).fill(1);
  for (let i = 2; i <= rowIndex; i++) {
    for (let j = i - 1; j >= 1; j--) row[j] += row[j - 1]; // right to left, so row[j - 1] is still the old row
  }
  return row;
}

pascalRow(5); // [1, 5, 10, 10, 5, 1]

pascalRows costs O(n²) time and space. In pascalRow the inner loop must run right to left: going left to right would read a row[j - 1] that has just been overwritten with a value from the new row. The same pattern, one array updated from the right, is the rolling-array trick in knapsack problems. Add % m to the addition and the table gives binomials modulo any m, prime or not, in O(n²).

One entry without the table. C(n, k) = n * (n-1) * ... * (n-k+1) / k! can be built step by step: after step i the running value is C(n - k + i, i), and the next value is the running value times (n - k + i + 1) divided by (i + 1). The division is exact at every step, because the value after the step is the integer C(n - k + i + 1, i + 1), so the product before the division is a multiple of the divisor. That is an O(k) loop with no table.

function binomial(n, k) {
  k = Math.min(k, n - k);                     // C(n, k) equals C(n, n - k): do fewer steps
  let result = 1;
  for (let i = 1; i <= k; i++) {
    result = (result * (n - k + i)) / i;      // exact division at every step, while the product is a safe integer
  }
  return result;
}

function binomialBig(n, k) {
  k = Math.min(k, n - k);
  let result = 1n;
  for (let i = 1; i <= k; i++) {
    result = (result * BigInt(n - k + i)) / BigInt(i);
  }
  return result;
}

binomial(10, 3);        // 120
binomial(55, 26);       // 3560597348629859.5 (not even an integer)
binomialBig(55, 26);    // 3560597348629860n

Counting: stars and bars, Catalan numbers

Many "how many ways" questions reduce to a binomial. Two families come up so often that you should recognise them on sight.

Stars and bars: splitting identical items into bins

How many ways can n identical items go into k labelled bins, with a bin allowed to be empty? Lay the n items in a row as stars and place k - 1 dividers (bars) among them; the arrangement is determined by which of the n + k - 1 positions hold bars. So the count is C(n + k - 1, k - 1). Equivalently it counts the non-negative integer solutions of x₁ + ... + x_k = n. If every bin must hold at least one item, give each bin one item first, and the count becomes C(n - 1, k - 1).

For example, the number of solutions of x + y + z = 7 with non-negative integers is C(9, 2) = 36. The same reasoning counts paths on a grid. A path from the top-left to the bottom-right of an m by n grid that moves only right or down makes m - 1 down moves and n - 1 right moves in some order, so there are C(m + n - 2, m - 1) paths. That is the closed form behind the "Unique Paths" table problem.

function countSolutions(total, variables) {
  return binomial(total + variables - 1, variables - 1); // non-negative integers summing to total
}

function uniquePaths(rows, cols) {
  return binomial(rows + cols - 2, rows - 1);
}

countSolutions(7, 3); // 36
uniquePaths(3, 7);    // 28

Catalan numbers: balanced structures

Count the valid strings made of n pairs of parentheses. Take such a string; its first character is "(", and that bracket closes at some position, leaving a valid string of i pairs inside it and a valid string of the remaining n - 1 - i pairs after it. Every valid string splits in exactly one way, so C_n = the sum over i from 0 to n - 1 of C_i * C_n-1-i, with C₀ = 1. The values run 1, 1, 2, 5, 14, 42, 132, 429.

The same recurrence counts the binary trees with n nodes and the structurally different binary search trees on n keys: pick the root, put i nodes on the left and n - 1 - i on the right, multiply the counts. It counts the ways to triangulate a polygon and the monotone lattice paths that never cross the diagonal. When a problem says "number of structurally unique" and the structure splits into a left part and a right part, think Catalan.

The closed form. Think of a valid string as a path of 2n steps, "(" going up and ")" going down, that never goes below zero and ends at zero. All paths with n ups and n downs number C(2n, n). A path that does go below zero first touches the level -1. Reflect the part of the path after that first touch, swapping ups and downs: the reflected path ends at -2 instead of 0, and the correspondence is reversible. So the bad paths are in one-to-one correspondence with all paths from 0 to -2, which number C(2n, n + 1). The valid ones are C(2n, n) - C(2n, n + 1) = C(2n, n) / (n + 1).

function catalanByRecurrence(n) {
  const c = new Array(n + 1).fill(0);
  c[0] = 1;
  for (let i = 1; i <= n; i++) {
    for (let left = 0; left < i; left++) c[i] += c[left] * c[i - 1 - left];
  }
  return c[n];
}

function catalan(n) {
  let c = 1n;
  for (let k = 0n; k < BigInt(n); k++) {
    c = (c * 2n * (2n * k + 1n)) / (k + 2n); // C(k+1) = C(k) * 2(2k+1) / (k+2), exact at every step
  }
  return c;
}

catalanByRecurrence(5); // 42
catalan(19);            // 1767263190n, the answer to "unique BSTs" for n = 19

The multiplicative step comes from dividing C(2n + 2, n + 1) / (n + 2) by C(2n, n) / (n + 1), which simplifies to 2(2n + 1) / (n + 2); the division is exact because the result is an integer. The recurrence costs O(n²) and is the one to write on a whiteboard because it is the definition. In plain Numbers it is exact up to C₃₀ = 3814986502092304, and beyond that you need the BigInt version or a modulus. The multiplicative form with Numbers is no safer: the product before the division is already above 2⁵³ from n = 29, and it first gives a wrong value at n = 31.

Matrix exponentiation for linear recurrences

Fibonacci with n up to 10¹⁸ cannot be filled in a loop, and the table-based DP is O(n). The recurrence F(n) = F(n - 1) + F(n - 2) is linear, and a linear step can be written as a matrix. Keep the last two values as a column vector. One step turns (F(n), F(n - 1)) into (F(n + 1), F(n)):

| F(n+1) |   | 1 1 |   | F(n)   |
| F(n)   | = | 1 0 | * | F(n-1) |

Applying the matrix n times multiplies by Mⁿ, and Mⁿ is computed in O(log n) matrix multiplications by the fast exponentiation loop, because matrix multiplication is associative. For a recurrence of order k, f(n) = c₁ f(n - 1) + ... + c_k f(n - k), the matrix is k by k: the first row holds the coefficients and the sub-diagonal holds ones that shift the older values down. Each multiplication costs O(k³), so the whole computation is O(k³ log n).

function matMul(A, B, m) {
  const k = A.length;
  const C = Array.from({ length: k }, () => new Array(k).fill(0n));
  for (let i = 0; i < k; i++) {
    for (let t = 0; t < k; t++) {
      if (A[i][t] === 0n) continue;
      for (let j = 0; j < k; j++) C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % m;
    }
  }
  return C;
}

function matPow(M, e, m) {
  const k = M.length;
  let result = Array.from({ length: k }, (_, i) => Array.from({ length: k }, (_, j) => (i === j ? 1n : 0n)));
  let base = M;
  while (e > 0n) {
    if (e & 1n) result = matMul(result, base, m);
    base = matMul(base, base, m);
    e >>= 1n;
  }
  return result;
}

function linearRecurrenceMod(coeffs, initial, n, m) {
  const k = coeffs.length;
  if (n < k) return mod(initial[n], m);
  const M = BigInt(m);
  const companion = Array.from({ length: k }, () => new Array(k).fill(0n));
  for (let j = 0; j < k; j++) companion[0][j] = BigInt(mod(coeffs[j], m));
  for (let i = 1; i < k; i++) companion[i][i - 1] = 1n; // shifts f(n-1) down into the next slot
  const power = matPow(companion, BigInt(n), M);
  let total = 0n;
  for (let j = 0; j < k; j++) total += power[k - 1][j] * BigInt(mod(initial[k - 1 - j], m));
  return Number(total % M);
}

linearRecurrenceMod([1, 1], [0, 1], 10, 1000000007);          // 55, the Fibonacci number F(10)
linearRecurrenceMod([1, 1, 1], [0, 1, 1], 10, 1000000007);    // 149, the Tribonacci number T(10)

The state vector at step t is (f(t + k - 1), ..., f(t)), which is the initial values listed in reverse, and after n steps the last entry is f(n); that is why the final loop multiplies the last row of the power by the reversed initial values.

Dry run: M⁵ for Fibonacci

Mⁿ has F(n + 1) and F(n) in its first row and F(n) and F(n - 1) in its second, so the result [[8,5],[5,3]] says F(6) = 8, F(5) = 5 and F(4) = 3. Note also what plain Numbers do here: F(78) = 8944394323791464 is the last Fibonacci number below 2⁵³. A Number loop computes F(79) as 14472334024676220, and the true value is 14472334024676221. Without a modulus, use BigInt; with one, use the BigInt matrix above.

Fast doubling is a faster special case for Fibonacci only. Two identities, F(2k) = F(k) * (2 F(k+1) - F(k)) and F(2k+1) = F(k)² + F(k+1)², let you go from the pair for k to the pair for 2k and 2k + 1, halving n each time. It needs no matrix.

function fibDoubling(n, m) { // n and m are BigInt; returns [F(n), F(n+1)] mod m
  if (n === 0n) return [0n, 1n % m];
  const [a, b] = fibDoubling(n >> 1n, m);
  const c = (a * (((2n * b - a) % m) + m)) % m;  // F(2k); the +m keeps the factor non-negative
  const d = (a * a + b * b) % m;                 // F(2k+1)
  return n & 1n ? [d, (c + d) % m] : [c, d];
}

fibDoubling(10n, 1000000007n)[0]; // 55n

How to recognise it. The statement defines each term from the previous few with fixed coefficients and asks for a term at a huge index, usually modulo a prime. Climbing stairs with 1 or 2 steps, tilings of a 2 by n board with dominoes, and binary strings of length n with no two adjacent ones are all Fibonacci in disguise, and with n up to 10¹⁸ this is the intended tool.

Josephus: the circle that shrinks

Stand n people in a circle numbered 0 to n - 1. Starting at person 0, count k people and remove the k-th, then keep counting from the next person, until one is left. Simulating with an array costs O(n * k) or O(n²) with splice. The recurrence is much shorter.

Let J(n) be the position of the survivor among n people. The first person removed is at position (k - 1) mod n, and counting restarts at position k mod n. Relabel the remaining n - 1 people so that the one who starts the new count is 0: the person with new label j has old label (j + k) mod n. The survivor of the smaller circle is J(n - 1) in the new labels, so in the old labels

J(1) = 0
J(n) = (J(n - 1) + k) mod n

function josephus(n, k) {
  let survivor = 0;                               // J(1), 0-indexed
  for (let size = 2; size <= n; size++) {
    survivor = (survivor + k) % size;
  }
  return survivor + 1;                            // the people are named 1..n in the usual statement
}

josephus(7, 3); // 4

Dry run: josephus(7, 3)

Each cell is the previous one plus 3, modulo the size in its column. The result is index 3, which is person 4. The simulation agrees: people 3, 6, 2, 7, 5, 1 are removed in that order and 4 is left.

Cost. O(n) time, O(1) space. The k = 2 case has a closed form: if 2^m is the largest power of two not above n, the survivor is 2 * (n - 2^m) + 1. In binary this is "move the leading 1 to the end". 1 << (31 - Math.clz32(n)) finds 2^m for n below 2³¹ without a floating-point logarithm.

function josephusTwo(n) {
  const highest = 1 << (31 - Math.clz32(n)); // largest power of two not above n
  return 2 * (n - highest) + 1;
}

josephusTwo(7); // 7
josephusTwo(6); // 5

Bases, Roman numerals and number to words

These are "convert a representation" problems. They have no cleverness; the marks go to clean handling of zero, negatives and the grouping loop.

Converting to another base

The last digit of n in base b is n mod b, and the remaining digits are the representation of floor(n / b). So repeat: take the remainder, divide, and stop when nothing is left. Digits come out from least to most significant, so reverse at the end.

function toBase(n, base) {
  if (n === 0) return "0";                          // the loop below would produce an empty string
  const symbols = "0123456789abcdefghijklmnopqrstuvwxyz";
  let rest = Math.abs(n);
  const digits = [];
  while (rest > 0) {
    const digit = rest % base;
    digits.push(symbols[digit]);
    rest = (rest - digit) / base;                   // exact: a multiple of base divided by base
  }
  return (n < 0 ? "-" : "") + digits.reverse().join("");
}

function fromBase(text, base) {
  const negative = text[0] === "-";
  let value = 0;
  for (const ch of negative ? text.slice(1) : text) {
    value = value * base + parseInt(ch, 36);       // each step shifts left one digit and adds the new one
  }
  return negative ? -value : value;
}

toBase(156, 2);       // "10011100"
toBase(-100, 7);      // "-202"
fromBase("10011100", 2); // 156

n.toString(base) and parseInt(text, base) exist and are the right tool in real code; the interview version asks you to write the loop. The loop costs O(log_b n). Excel column titles are base 26 with no zero digit ("A" is 1, "Z" is 26, "AA" is 27), so subtract 1 before taking each remainder. Forgetting that shift is the usual bug: 26 would become an empty digit.

function columnTitle(n) {
  const letters = [];
  while (n > 0) {
    n -= 1;                                          // shift to 0..25 so that Z is 25, not 0
    letters.push(String.fromCharCode(65 + (n % 26)));
    n = Math.floor(n / 26);
  }
  return letters.reverse().join("");
}

function columnNumber(title) {
  let n = 0;
  for (const ch of title) n = n * 26 + (ch.charCodeAt(0) - 64);
  return n;
}

columnTitle(28);   // "AB"
columnTitle(701);  // "ZY"
columnNumber("AB"); // 28

Roman numerals

To write n, go down a table of the thirteen values that have their own symbol (the subtractive forms 900, 400, 90, 40, 9, 4 included) and take each as many times as it fits. To read a numeral, add each symbol, but subtract it when the symbol to its right is larger, as in the I of IV.

const ROMAN = [
  [1000, "M"], [900, "CM"], [500, "D"], [400, "CD"], [100, "C"], [90, "XC"], [50, "L"],
  [40, "XL"], [10, "X"], [9, "IX"], [5, "V"], [4, "IV"], [1, "I"],
];

function toRoman(n) {
  let out = "";
  for (const [value, symbol] of ROMAN) {
    while (n >= value) {
      out += symbol;
      n -= value;
    }
  }
  return out;
}

function fromRoman(text) {
  const value = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };
  let total = 0;
  for (let i = 0; i < text.length; i++) {
    const current = value[text[i]];
    const next = value[text[i + 1]] ?? 0;
    total += current < next ? -current : current;
  }
  return total;
}

toRoman(1994);     // "MCMXCIV"
fromRoman("MCMXCIV"); // 1994

Number to words

English reads a number in groups of three digits, each followed by a scale word: 1234567 is "1" million, "234" thousand, "567". So split from the right with % 1000, turn each group into words, add the scale, and join the groups from the largest down. A group under 1000 is the hundreds digit, then a number under 100 that is either in the table of 1 to 19 or a tens word plus a ones word.

const BELOW_TWENTY = [
  "", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven",
  "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen",
];
const TENS = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"];
const SCALES = ["", "Thousand", "Million", "Billion"];

function threeDigits(n) {
  const parts = [];
  if (n >= 100) {
    parts.push(BELOW_TWENTY[Math.floor(n / 100)], "Hundred");
    n %= 100;
  }
  if (n >= 20) {
    parts.push(TENS[Math.floor(n / 10)]);
    n %= 10;
  }
  if (n > 0) parts.push(BELOW_TWENTY[n]);
  return parts.join(" ");
}

function numberToWords(num) {
  if (num === 0) return "Zero";
  const parts = [];
  for (let scale = 0; num > 0; scale++) {
    const group = num % 1000;
    if (group > 0) parts.push(threeDigits(group) + (SCALES[scale] ? " " + SCALES[scale] : ""));
    num = Math.floor(num / 1000);
  }
  return parts.reverse().join(" ");
}

numberToWords(1234567); // "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
numberToWords(1000010); // "One Million Ten"

Reverse integer, digits and overflow

Reversing digits is a loop of "take the last digit, shift the result". In JavaScript the interesting part is the 32-bit limit that the statement imposes, because the language itself does not overflow here. A 32-bit integer is at most 2147483647 in magnitude, so its reverse has at most ten digits and is below 10¹⁰, far inside the safe range. So you can compute the reverse in full and test the range at the end, with no need for the pre-check that other languages require.

function reverseInteger(x) {
  let rest = Math.abs(x);
  let reversed = 0;
  while (rest > 0) {
    reversed = reversed * 10 + (rest % 10); // append the last digit of rest
    rest = Math.floor(rest / 10);           // and drop it
  }
  if (reversed > 2 ** 31 - 1) return 0;      // out of the signed 32-bit range
  return x < 0 ? -reversed : reversed;
}

reverseInteger(123);         // 321
reverseInteger(-120);        // -21
reverseInteger(1534236469);  // 0, since 9646324351 is above 2^31 - 1

Why no separate check for the negative side: a negative result would need a reverse of exactly 2³¹ = 2147483648 to reach -2³¹, and the input that reverses to it, 8463847412, is itself out of range. Working with Math.abs avoids the negative-remainder trap: -123 % 10 is -3, and Math.floor(-123 / 10) is -13, not -12. Use Math.trunc if you want to work on the signed value directly.

Palindrome number without a string. Reverse only the second half. Stop when the reversed half is at least as large as what remains, which happens at the middle, and then compare, ignoring the middle digit when the length is odd. Negative numbers and numbers that end in 0 (except 0 itself) are never palindromes, so rule them out first.

function isPalindromeNumber(x) {
  if (x < 0 || (x % 10 === 0 && x !== 0)) return false;
  let reversedHalf = 0;
  while (x > reversedHalf) {
    reversedHalf = reversedHalf * 10 + (x % 10);
    x = Math.floor(x / 10);
  }
  return x === reversedHalf || x === Math.floor(reversedHalf / 10);
}

isPalindromeNumber(12321); // true

Digit tricks that replace a loop

• Digital root. Repeatedly adding the digits of n until one digit is left gives 0 for n = 0 and 1 + (n - 1) % 9 otherwise. The reason: 10 leaves remainder 1 when divided by 9, so a number and its digit sum leave the same remainder when divided by 9, and the repeated sum is the one-digit number with that remainder (9, not 0, when n is a positive multiple of 9).
• Trailing zeros of n!. Each trailing zero is a factor 10 = 2 * 5, and 2s are far more plentiful than 5s among the factors of 1 to n, so the count of 5s decides. Multiples of 5 contribute one, multiples of 25 a second, of 125 a third: the answer is the sum of floor(n / 5ⁱ). The loop runs log₅ n times, and n = 1000000 takes 8 steps.
• Power of three without a loop. The largest power of three below 2³¹ is 3¹⁹ = 1162261467. Since 3 is prime, the divisors of 3¹⁹ are exactly the powers of three up to 3¹⁹, so for a positive 32-bit n, 1162261467 % n === 0 tests it. The same trick works for any prime base, and is not valid for powers of a composite such as 4.
• Digit count. String(n).length, or a loop that divides by 10. Not Math.log, for the reason in the warning near the start.

function digitalRoot(n) {
  return n === 0 ? 0 : 1 + ((n - 1) % 9);
}

function trailingZeroes(n) {
  let count = 0;
  for (let p = 5; p <= n; p *= 5) count += Math.floor(n / p);
  return count;
}

function isPowerOfThree(n) {
  return n > 0 && 1162261467 % n === 0;
}

digitalRoot(38);        // 2: 3 + 8 = 11, then 1 + 1 = 2
trailingZeroes(100);    // 24: 20 multiples of 5 plus 4 multiples of 25
isPowerOfThree(27);     // true

Happy numbers and ugly numbers

Happy numbers

Replace a number by the sum of the squares of its digits, repeatedly. It is happy if the sequence reaches 1, and unhappy otherwise. The question is why "otherwise" does not mean "runs forever without repeating": the sequence cannot grow without bound. A number with d digits maps to at most 81 * d. For d at least 4 that is smaller than the number itself (81 * 4 = 324 < 1000), so while the value is 1000 or more it strictly decreases, and once it is below 1000 the next value is at most 243 (the largest sum for three digits is 81 * 3). So every sequence ends up among a finite set of values and must repeat. It either reaches 1, which maps to itself, or runs into a cycle. Checking every number below 1000 by program shows that the only cycle other than the fixed point 1 is 4, 16, 37, 58, 89, 145, 42, 20, back to 4.

function digitSquareSum(n) {
  let sum = 0;
  while (n > 0) {
    const d = n % 10;
    sum += d * d;
    n = Math.floor(n / 10);
  }
  return sum;
}

function isHappy(n) {
  let slow = n;
  let fast = digitSquareSum(n);
  while (fast !== 1 && slow !== fast) {  // stop at 1, or when the two pointers meet in a cycle
    slow = digitSquareSum(slow);
    fast = digitSquareSum(digitSquareSum(fast));
  }
  return fast === 1;
}

isHappy(19); // true: 19, 82, 68, 100, 1
isHappy(2);  // false: 2, 4, 16, 37, 58, 89, 145, 42, 20, 4, ...

This is cycle detection on a function, the same fast and slow pointer idea as for linked lists. The alternative stores every value seen in a Set and stops on a repeat. It is simpler to write, and the fast and slow version needs O(1) extra space where the set needs space for every value seen. A 32-bit input drops below 1000 after the first step (at most 81 * 10 = 810), and from there every value is at most 243, so a 1 or a repeat must appear within 244 more steps. In a check over a large sample of 32-bit inputs the longest run was 20 steps.

Ugly numbers

An ugly number has no prime factors other than 2, 3 and 5. To test one, divide out 2, 3 and 5 as long as they divide n, and check that 1 remains. Zero and negatives are not ugly.

To list the n-th ugly number, do not test integers one by one: the n-th ugly number can be far larger than n. Instead build the sequence in order. Every ugly number above 1 is 2, 3 or 5 times a smaller ugly number, so the next one is the smallest among 2 * u_a, 3 * u_b and 5 * u_c, where a, b and c are pointers into the list of ugly numbers found so far, each pointing at the first entry whose multiple is not yet in the list. After adding a value, advance every pointer whose multiple equals it: 6 is both 2 * 3 and 3 * 2, and advancing only one pointer would add 6 twice.

function isUgly(n) {
  if (n <= 0) return false;
  for (const p of [2, 3, 5]) {
    while (n % p === 0) n /= p;
  }
  return n === 1;
}

function nthUgly(n) {
  const ugly = [1];
  let i2 = 0;
  let i3 = 0;
  let i5 = 0;
  while (ugly.length < n) {
    const next = Math.min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5);
    ugly.push(next);
    if (next === ugly[i2] * 2) i2++;  // separate ifs, not else-if: a tie advances every pointer that produced it
    if (next === ugly[i3] * 3) i3++;
    if (next === ugly[i5] * 5) i5++;
  }
  return ugly[n - 1];
}

nthUgly(10); // 12

Dry run: the first twelve ugly numbers

The list begins 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16. Cost: O(n) time and space, with three pointer moves per step at most. The generalisation to a list of k primes ("super ugly numbers") keeps k pointers and takes O(n * k).

Probability basics

Interview probability is mostly counting, so it belongs next to binomials. Three ideas cover most of it.

• Favourable over total, with equally likely outcomes. The chance of rolling a sum of 7 with two dice is the number of (a, b) pairs with a + b = 7 (6 of them) divided by 36 outcomes. The skill is counting both numbers correctly, with the same notion of "outcome" in both.
• The complement. "At least one" is cheapest as 1 minus "none". In a room of n people, the chance that all birthdays differ is the product of (365 - i) / 365 for i from 0 to n - 1, and the chance that at least two match is 1 minus that. It passes one half at n = 23.
• Linearity of expectation. The expected value of a sum is the sum of the expected values, even when the parts are dependent. In a random permutation of n items, each position holds its own item with probability 1 / n, so the expected number of fixed points is n * (1 / n) = 1 for every n. The coupon collector's expected number of draws to see all n kinds is n * (1 + 1/2 + ... + 1/n), because once k kinds are collected, the wait for a new one has expected length n / (n - k).

function diceWays(dice, sides, target, m = Infinity) { // ways for the dice to total target; m = Infinity keeps the counts exact
  let ways = new Array(target + 1).fill(0);
  ways[0] = 1;
  for (let d = 0; d < dice; d++) {
    const next = new Array(target + 1).fill(0);
    for (let sum = 0; sum <= target; sum++) {
      if (ways[sum] === 0) continue;
      for (let face = 1; face <= sides && sum + face <= target; face++) {
        next[sum + face] = (next[sum + face] + ways[sum]) % m;
      }
    }
    ways = next;
  }
  return ways[target];
}

function sharedBirthdayProbability(people, days = 365) {
  let allDifferent = 1;
  for (let i = 0; i < people; i++) allDifferent *= (days - i) / days;
  return 1 - allDifferent;
}

function couponCollectorExpected(kinds) {
  let expected = 0;
  for (let k = 0; k < kinds; k++) expected += kinds / (kinds - k);
  return expected;
}

diceWays(2, 6, 7) / 6 ** 2;       // 6 / 36, about 0.1667
sharedBirthdayProbability(23);    // about 0.5073
couponCollectorExpected(6);       // 14.7, the expected rolls of a die to see every face

diceWays is a DP over the number of dice and the running total, with O(dice * target * sides) time and O(target) space; it only adds, so with a modulus it is safe in plain Numbers. For probabilities, divide the count by sides^dice, while that is small enough to represent. Other probability questions that look like sampling, such as building a fair generator for 1 to 10 out of one for 1 to 7, use rejection: draw, and throw away outcomes that would make the result uneven, then repeat. Their expected cost is the reciprocal of the acceptance probability, and computing that is a counting exercise like the ones above.

Recognizing it in an unseen problem

• The statement says "modulo 10⁹ + 7", or "return the result modulo": all arithmetic is residues, products go through BigInt or mulMod, and any division becomes a multiplication by an inverse.
• An exponent, index or repetition count is 10⁹ or more: look for O(log n) with fast exponentiation, or with a matrix when the quantity follows a linear recurrence.
• "Number of ways" with identical items, grid paths or choices of a subset: a binomial. "Number of distinct trees or bracket structures": Catalan.
• Divisibility, "every k-th", cycles of equal length, measuring with fixed jugs, simplifying a ratio: gcd and lcm.
• Many primality questions or "primes up to n": sieve. One large number: trial division up to the square root, and factorization with the leftover rule.
• A people-in-a-circle problem where each round removes one: Josephus with the recurrence on the circle size.
• The input is a number but the work is on its digits, or the output is its text: the loop that takes % 10 and Math.floor(x / 10), or the grouping loop for words and bases.
• A process on numbers that repeats a function: either it reaches a fixed point or it cycles, and fast and slow pointers or a set decide which.
• The answer is an average, a chance or an expected value: write the sample space, count favourable outcomes, or break the quantity into parts and use linearity.

Before coding any of it, test the idea on the smallest cases you can enumerate. These problems are short, so a wrong formula does not look wrong until you compare it with a case you counted by hand.