Binomial Coefficient Problem

The problem, simply

You get two numbers, n and k. Count how many different groups of k things you can pick from n things. Order does not matter: picking Ann then Bob is the same group as Bob then Ann.

This count is written C(n, k) and is called "n choose k". The answer can be huge, so most judges want it modulo 10^9 + 7. If k is bigger than n, the answer is 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

Turn the story into a rule: C(n, k) = C(n - 1, k - 1) + C(n - 1, k). The first part is "the last friend comes", the second is "the last friend stays home".

1. If k == 0 or k == n, there is one way. Return 1.
2. Otherwise return C(n - 1, k - 1) + C(n - 1, k).

class Solution {
    public int nCr(int n, int k) {
        if (k > n) return 0;                    // cannot pick more than we have
        if (k == 0 || k == n) return 1;         // pick nobody, or pick everybody
        // last friend comes + last friend stays home
        return nCr(n - 1, k - 1) + nCr(n - 1, k);
    }
}

How long it takes: the calls branch in two, and the tree has about 2 * C(n, k) circles, which grows up to O(2^n). Extra room: the chain of waiting calls is at most n long, O(n).

Way 2: the clever way

The tree asks the same questions many times. Build the pyramid from the top instead, one row at a time. Row i only needs row i - 1, so keep one row in an array dp, where dp[j] is C(i, j).

1. Start with dp = [1, 0, 0, ...]. That is row 0.
2. For each row i from 1 to n, update dp[j] = dp[j] + dp[j - 1] for j going from right to left.
3. The answer is dp[k].

Why right to left? dp[j] needs the old dp[j - 1], from the row above. If we went left to right we would have already changed it.

class Solution {
    public int nCr(int n, int k) {
        final long MOD = 1_000_000_007L;
        if (k > n) return 0;
        k = Math.min(k, n - k);               // picking k to go = picking n-k to stay
        long[] dp = new long[k + 1];          // dp[j] = C(row, j) for the current row
        dp[0] = 1;                            // row 0
        for (int i = 1; i <= n; i++) {
            // right to left, so dp[j - 1] still holds the row above
            for (int j = Math.min(i, k); j >= 1; j--) {
                dp[j] = (dp[j] + dp[j - 1]) % MOD;
            }
        }
        return (int) dp[k];
    }
}

How long it takes: n rows with at most k boxes each, O(n * k). Extra room: one row of k + 1 boxes, O(k).

Watch out for

• k > n must give 0, and k = 0 must give 1.
• Without the modulo, int overflows quickly. C(34, 17) is already more than 2 billion.
• Do not compute n! / (k! * (n - k)!) with plain numbers. The factorials overflow long before the answer does.

What interviewers ask next

• Can you do it in O(k) time without a table? Yes: start with res = 1 and for i = 0..k-1 do res = res * (n - i) / (i + 1). The division is always exact at each step, but it does not mix with a modulo.
• Many queries with a prime modulo and n up to a million? Precompute factorials and their inverses with Fermat's little theorem (a^(p-2) mod p). Then each answer is O(1).
• n is huge (like 10^18) and the prime p is small? Use Lucas' theorem: write n and k in base p and multiply the small binomials digit by digit.
• Where else does this show up? Counting grid paths (C(m + n, n)), the number of subsets of size k, and the coefficients of (a + b)^n.

Remember this

Grown-up words: the number pyramid is Pascal's triangle, "n choose k" is the binomial coefficient, the repeated questions are overlapping subproblems, and keeping one row is a rolling array.