Friends Pairing Problem

The problem, simply

There are n friends. Each friend either stays single or pairs up with exactly one other friend. A friend can be in at most one pair. Count all the different ways this can happen.

Pairs have no order: A with B is the same pair as B with A. The answer grows fast, so judges want it modulo 10^9 + 7.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write the story as recursion. Look at the last friend.

1. f(1) = 1 and f(2) = 2.
2. Last friend alone: f(n - 1) ways for the rest.
3. Last friend in a pair: n - 1 partner choices, then f(n - 2) ways for the rest.
4. Add them.

class Solution {
    public long countFriendsPairings(int n) {
        if (n <= 2) return n;                            // f(1) = 1, f(2) = 2
        long alone = countFriendsPairings(n - 1);        // last friend stays single
        long paired = (n - 1) * countFriendsPairings(n - 2);  // picks one of n-1 partners
        return alone + paired;
    }
}

How long it takes: two calls each time, like Fibonacci, so up to O(2^n) calls. Extra room: the chain of calls, O(n).

Way 2: the clever way

Every f(i) only needs f(i - 1) and f(i - 2). Compute them from small to big and keep just the last two.

1. prev2 = f(1) = 1, prev1 = f(2) = 2.
2. For i from 3 to n: cur = prev1 + (i - 1) * prev2, then slide.
3. Return prev1.

class Solution {
    public long countFriendsPairings(int n) {
        final long MOD = 1_000_000_007L;
        if (n <= 2) return n;
        long prev2 = 1;   // f(1)
        long prev1 = 2;   // f(2)
        for (int i = 3; i <= n; i++) {
            // alone: f(i-1); with a partner: (i-1) choices times f(i-2)
            long cur = (prev1 + (long) (i - 1) * prev2) % MOD;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

How long it takes: one step per friend, O(n). Extra room: two numbers, O(1).

Watch out for

• Overflow. f(20) is already over 23 billion, which does not fit in an int. Use long and the modulo.
• Multiply (i - 1) * prev2 as long before taking the modulo.
• f(0) is 1 if the judge asks for it (nobody, one way).

What interviewers ask next

• Groups of up to three? The newest friend is alone, picks 1 partner, or picks 2: f(n) = f(n-1) + (n-1) f(n-2) + C(n-1, 2) f(n-3).
• Everyone must be in a pair (no singles)? For even n the answer is (n-1) x (n-3) x ... x 1. The newest picks a partner, and nobody may stay alone.
• Where else does this sequence show up? It counts shuffles that undo themselves when done twice (involutions), and phone lines where each line connects at most two people. Quant interviews sometimes ask it in that form.
• Print all arrangements? Backtracking: for the first free friend, try alone, then try each later free friend as a partner.

Remember this

Grown-up words: a set of pairs that share nobody is a matching in a complete graph, the count is the telephone numbers or involution numbers, the faded repeats are overlapping subproblems, and keeping two numbers is space optimization.