Count the Number of Infection Sequences

Count the Number of Infection Sequences

What is this problem about?

The Count the Number of Infection Sequences coding problem describes a scenario where some children in a row are already "infected." Every second, an uninfected child who is adjacent to at least one infected child becomes infected. If a child has two infected neighbors, they can be infected by either one.

The goal is to find the total number of distinct sequences in which all children can become infected.

Why is this asked in interviews?

This "Hard" problem is used by Meta, Microsoft, and SAP to test combinatorics and permutations of multisets. It requires breaking down the gaps between initially infected children into independent sub-problems. It evaluations whether a candidate can use the formula for permutations with identical items and understand the power of 2 rule for "double-sided" infections.

Algorithmic pattern used

This is a Combinatorial Counting problem.

1. Identify Gaps: Let $G_1, G_2, \dots, G_k$ be the lengths of uninfected children between infected ones.
2. Determine Ways for each Gap:
   • For an end gap (e.g., before the first infected child), there is only 1 sequence (it must infect from the inside out).
   • For a middle gap of length $L$, each step can infect from either the left or right side (except the last child). This results in $2^{L-1}$ ways.
3. Combine Sequences: You have a total of $N_{uninfected}$ steps to take. This is a permutation of all steps, where steps within the same gap must maintain their relative order.
4. Total = $\frac{(N_{uninfected})!}{G_1! G_2! \dots G_k!} imes \prod 2^{G_{middle}-1}$.

Example explanation

Children: [I, U, U, I] (I=Infected, U=Uninfected)

1. One middle gap of length 2.
2. Ways for this gap: $2^{2-1} = 2$ (Left then Right, or Right then Left).
3. Total steps = 2.
4. Formula: $\frac{2!}{2!} imes 2 = 2$. Sequences: [Child 1, Child 2] or [Child 2, Child 1].

Common mistakes candidates make

• Failing to handle end gaps: Treating the ends of the row as if they have two infection sources.
• Modulo errors: Not using modular inverse for the factorial divisions.
• Miscounting steps: Forgetting that the "total steps" is the sum of all uninfected children.

Interview preparation tip

This is a "Divide and Conquer" style combinatorics problem. Solve for the local "ways" within each independent group first, then use the "General Permutation" formula to merge the groups together. This pattern appears in many "total number of sequences" problems.