DSA Notes

Math

Combinatorics

Count arrangements without listing them.

The idea

The number of ways to choose k items out of n is C(n, k) = n! / (k! · (n−k)!). Answers are usually asked modulo a prime p, where division becomes multiplication by a modular inverse: a⁻¹ = a^(p−2) mod p.

Precompute factorials and inverse factorials once; every C(n, k) is then O(1).

Stars and bars: sharing n identical items among k children, where a child may get none, is the same as placing k−1 dividers among the items: C(n + k − 1, k − 1) ways. If every child must get at least one, it is C(n − 1, k − 1).

Sample problem

62. Unique Paths ↗ Medium

A robot stands in the top-left cell of an m × n grid and can only move right or down. Count the different paths to the bottom-right cell.

m = 3, n = 7
output = 28

Why the solution works

A table that adds “paths from above” and “paths from the left” works, but the count can be seen directly.

Every path consists of exactly m−1 downs and n−1 rights; only their order differs. Choosing which of the m+n−2 moves are the downs fixes the path, so the answer is the binomial coefficient C(m+n−2, m−1).

The loop builds that coefficient one factor at a time. After step i the value is C(total−k+i, i), itself a whole number, so the division is always exact. Using the smaller of m−1 and n−1 as k keeps the loop short.

Complexity: O(min(m, n)) time, O(1) memory.

Watch out

  • The a^(p−2) inverse only works when the modulus is prime.
  • Precompute far enough: stars and bars needs factorials up to n + k.
  • After a subtraction add MOD before taking the remainder, so the result is not negative.
Watch it run

Try your own input

Practise on LeetCode