We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count the Number of Infection Sequences

Number: 3224

Difficulty: Hard

Paid? No

Companies: SAP, Tekion

Problem Description

We are given an integer n representing people arranged in a line (indexed from 0 to n–1) and an array sick (sorted in increasing order) that marks the positions of people already infected. In a series of steps, one uninfected person adjacent to an infected person becomes infected. The process runs until every person is infected. An infection sequence is the order in which the initially healthy people become infected. We must count the number of valid infection sequences possible modulo 10^9+7.

Key Insights

  • The infection always proceeds from an infected person to one of its adjacent uninfected neighbors.
  • The line can be divided into segments: • The left boundary segment (before the first sick person), • The right boundary segment (after the last sick person), and • Interior gaps between consecutive sick people.
  • For a boundary segment there is only one way to infect these people (infection propagates in one fixed order).
  • For an interior segment (gap) with L uninfected people, initially both ends are available. However, the order in which the infections occur inside the gap is constrained – the infection must “peel” inward from both ends. One can show that the number of valid orders inside such a gap is 2^(L–1).
  • After separately “solving” each segment (each with its internal valid order count), the overall sequence is an interleaving of the infections from all segments. The count for interleavings is given by a multinomial coefficient: if the segments have lengths L1, L2, …, Lk then the number is (Sum Li)!/(L1! * L2! * … * Lk!).
  • The final answer is the product of the number of interleavings and the product of the choices for each interior segment. (Remember to take the result modulo 10^9+7).

Space and Time Complexity

Time Complexity: O(n) for precomputation of factorials up to n and processing the segments. Space Complexity: O(n) for storing factorials and inverse factorials modulo 10^9+7.

Solution

We first break the problem into parts:

  1. Count the total number X = n – (number of initially infected people). These are the uninfected people to be infected in some sequence.
  2. Determine the lengths of all segments:
    • Left boundary: sick[0] (if sick[0] > 0).
    • Right boundary: (n – 1) – sick[last] (if sick[last] < n – 1).
    • For every gap between sick[i] and sick[i+1], the length is (sick[i+1] – sick[i] – 1). For each interior gap, there are 2^(length – 1) infection orders internally.
  3. Count interleavings:
    • The infection order is a shuffle of the sequences from each segment. With segments lengths L1, L2, …, Lk (including boundary segments with fixed order count 1), the number of ways to interleave is (X)! / (L1! * L2! * … * Lk!).
  4. Multiply the interleaving count by the product of the counts for interior segments (each contributing a factor 2^(gap – 1)) and take modulo 10^9+7.
  5. Use modular arithmetic and precompute factorials and modular inverses for efficiency.

Data structures used:

  • Arrays for storing segment lengths.
  • Precomputed arrays for factorials and inverse factorials modulo mod. Algorithm:
  • Compute all segments lengths.
  • Precompute factorials up to X.
  • Compute the interleaving count using the multinomial formula.
  • Multiply by the contributions of interior segments: for each gap segment, multiply by 2^(gap_length – 1).
  • Return the final answer modulo 10^9+7.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with clear line-by-line comments.

MOD = 10**9 + 7

# Precompute factorials and inverse factorials modulo MOD
def precompute_factorials(n):
    fact = [1]*(n+1)
    inv_fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i % MOD
    inv_fact[n] = pow(fact[n], MOD-2, MOD)  # Fermat's little theorem
    for i in range(n, 0, -1):
        inv_fact[i-1] = inv_fact[i] * i % MOD
    return fact, inv_fact

def countInfectionSequences(n, sick):
    total_sick = len(sick)
    # Total number of initially uninfected people
    X = n - total_sick

    segments = []  # Will hold the lengths of each segment
    
    # Left boundary segment
    if sick[0] > 0:
        left_seg = sick[0]
        segments.append(left_seg)
    # Interior segments between sick people; these have two infected boundaries.
    interior_factors = 1  # For multiplication of 2^(L-1) factors
    for i in range(len(sick) - 1):
        gap = sick[i+1] - sick[i] - 1
        if gap > 0:
            segments.append(gap)
            # For an interior gap, update the multiplier with 2^(gap-1)
            interior_factors = (interior_factors * pow(2, gap - 1, MOD)) % MOD
    # Right boundary segment
    if sick[-1] < n - 1:
        right_seg = (n - 1) - sick[-1]
        segments.append(right_seg)
    
    # Precompute factorials up to X
    fact, inv_fact = precompute_factorials(X)
    
    # Calculate multinomial coefficient: X! / (prod(segment_factorials))
    interleavings = fact[X]
    for seg in segments:
        interleavings = (interleavings * inv_fact[seg]) % MOD
    
    # Final answer: interleavings * (product of interior factors)
    return (interleavings * interior_factors) % MOD

# Example usage:
#print(countInfectionSequences(5, [0,4]))  # Expected output: 4
#print(countInfectionSequences(4, [1]))    # Expected output: 3
← Back to All Questions