2954. Count the Number of Infection Sequences

Problem Description

In this problem, you are given two pieces of information: the number of children n standing in a queue and an array sick indicating the positions of children who are already infected with a contagious disease. The children are positioned in a 0-indexed queue from 0 to n - 1. The sick array is sorted in increasing order and represents the positions of the infected children.

A child who is infected can transmit the disease to immediate neighbors, one at a time, during each second that passes. The question is to find how many distinct sequences there can be in which all of the children eventually become infected.

It's important to note that the sequences only include the positions of children who were originally healthy and later became infected. The order in which each child gets sick constitutes an "infection sequence".

Your answer should be the total count of these sequences modulo 10^9 + 7, which is commonly done to handle very large numbers.

Intuition

The problem at first seems complex, but it can be broken down into smaller parts:

1. The infected children effectively split the queue into segments of uninfected children.
2. Each segment has a number of children who will get sick in a certain number of ways.
3. The transmission of the disease within each segment can happen in multiple ways, which we have to count.

We use combinatorial mathematics to approach this problem, visually expanding the queue into individual segments.

Firstly, we calculate the number of uninfected children in each segment created by the infected ones. The children at the beginning of the queue or at the end of the queue naturally have only one neighboring segment to consider, but those between the infected children need to consider both sides.

The intuition here is that there is a specific number of permutations of the children becoming sick, and it can be represented by factorial because the permutations of a number of items is just the factorial of that count.

To account for multiple ways a disease could spread in non-border segments, we consider that each child can infect either their left or right neighbor (except the first and last child, hence 2^(x-1) possibilities per segment).

We calculate the total permutations and then divide it by the permutations that are specific to each segment – as if the order within the segment doesn't matter, only the position at which an infection happened in the segment.

Finally, the multiplicative inverse and modular arithmetic are used to compute the final answer given the possible size of the numbers involved, using modulo 10^9 + 7.

The computation of factorial and multiplicative inverse modulo 10^9 + 7 is preprocessed to handle large numbers and to perform effective calculations under the modulo operator.

Learn more about Math and Combinatorics patterns.

Solution Approach

The solution involves multiple steps, each using specific algorithms, data structures, or mathematical patterns.

We start with preparing a list nums that contains the count of uninfected children in each segment. The calculation is done by taking the difference of the infected child's positions and subtracting one (because the positions are 0-indexed). We also concatenate -1 at the beginning and n at the end of the sick list to handle the start and end of the queue.

The number of possible infection sequences is effectively the permutations of all uninfected children becoming sick, initially calculated as s!, where s is the sum of all elements in nums indicating the total number of uninfected children. We use an array fac to precalculate the factorials up to n! modulo 10^9 + 7 to optimize for repeated calculations.

Next, we account for the fact that each segment is interchangeable, meaning that while there are s! ways to arrange the children, we divide this number by the factorial of each segment nums[i]! to correct for the overcounting.

For the segments between infected children (excluding the first and last segment), there are 2^(x-1) possible sequences for infecting x uninfected children within a segment, as each time an infection spreads, there are two choices - to the left or to the right (except for the first and last transmission).

We then apply the modular multiplicative inverse to find these factorials with respect to the given modulo 10^9 + 7. This ensures that we can divide numbers under modulo operations, which is otherwise not possible. To compute x!^-1 mod 10^9 +7, we use Fermat's Little Theorem which states that a^(-1) mod p = a^(p-2) mod p for a prime p, hence fac[x] * pow(fac[x], mod - 2, mod) % mod.

Finally, we need to compute the power of 2 modulo 10^9 + 7, which is done using the fast power algorithm, optimized to handle very large exponents by dividing the problem into smaller chunks.

The solution leverages these mathematical facts, combined with precomputation, modular arithmetic, and fast exponentiation to efficiently calculate the count of possible infection sequences.

This is how the implementation is structured in the given Python code, employing Python's pairwise function for calculating the differences between consecutive sick children, and iterating smartly over the nums array to avoid unnecessary calculations.

1mod = 10**9 + 7
2mx = 10**5
3fac = [1] * (mx + 1)
4for i in range(2, mx + 1):
5    fac[i] = fac[i - 1] * i % mod
6
7class Solution:
8    def numberOfSequence(self, n: int, sick: List[int]) -> int:
9        # Calculate the number of children in each segment
10        nums = [b - a - 1 for a, b in pairwise([-1] + sick + [n])]
11        # Start with the factorial of the total count of uninfected children
12        s = sum(nums)
13        ans = fac[s]
14        # Divide by the factorial of the count in each segment
15        for x in nums:
16            if x:
17                ans = ans * pow(fac[x], mod - 2, mod) % mod
18        # Multiply by 2^(count-1) for non-border segments
19        for x in nums[1:-1]:
20            if x > 1:
21                ans = ans * pow(2, x - 1, mod) % mod
22        # Return the final result
23        return ans

Example Walkthrough

Let's assume there are n = 7 children in the queue and the sick array is given as [1, 4]. This means children at positions 1 and 4 are already infected. The children are lined up as follows, where I represents an infected child and H represents a healthy child:

1H I H H I H H

Using the given approach:

1. Segmentation: We split the queue into segments determined by infected children positions. We get segments [0, 1], [2, 3] and [5, 6] which have lengths 1, 2, and 2 respectively after subtracting 1 to adjust for the 0-indexing.

2. Permutations of Infection: There is 1 child in the first segment, 2 in the second, and 2 in the third, totaling 5 uninfected children. The potential sequences in which all children can get sick is 5!, the factorial of the number of healthy children.

3. Correcting Overcounting: Since the order in which children in an individual segment get sick doesn't affect other segments, we divide the total permutations by the factorial of the size of each segment: 5! / (1! * 2! * 2!).

4. Multiplying for Choices: Only children in the non-border segments (middle segment in this case) have two neighbors to affect, providing 2^(count-1) ways to transmit the infection. There is only one non-border segment with 2 children, providing 2^(2-1) different ways.

5. Using Modular Arithmetic: Given the constraint of modulo 10^9 + 7, we work within this space to find 5! modulo 10^9 + 7, 1! modulo 10^9 + 7, and 2! modulo 10^9 + 7, along with the multiplicative inverses and powers of 2 as required.

Following these steps:

• The factorial values up to 7 are precomputed up to 10^9 + 7.
• The total permutations are calculated as: 𝑓𝑎𝑐[𝑠] = 𝑓𝑎𝑐[5] = 120.
• The overcounting is corrected by multiplying the answer with the modular inverses: 120 * modinv(fac[1]) * modinv(fac[2]) * modinv(fac[2]).
• Since the inverse of 1! is 1 and of 2! is 1 / 𝑓𝑎𝑐[2] = modinv(fac[2]), we compute these values using modular arithmetic.
• Lastly, for the middle segment, we adjust for the two ways transmission can occur: answer * pow(2, segment_length - 1, mod) which results in answer * pow(2, 1, mod).

Plugging the numbers in:

1Initial answer = fac[5] = 120
2Corrected answer = 120 * modinv(fac[1]) * modinv(fac[2]) * modinv(fac[2]) (mod 10^9 + 7)
3Corrected answer for non-border segment = 120 * 1 * 1/2 * 1/2 * 2 (mod 10^9 + 7)
4Final answer = 120 / 4 * 2 = 60 (mod 10^9 + 7)

Therefore, there are 60 distinct sequences in which all the children can get infected.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the numberOfSequence method is primarily determined by the following components:

1. The list comprehension that creates nums with the complexity O(k), where k is the number of elements in sick plus 2, for the additional elements added (-1 and n).

2. The loop iterating over nums to calculate ans. In the worst case, it iterates k-2 times (since nums was created from sick with two additional elements). Each iteration involves a modular multiplication and a modular exponentiation. Modular exponentiation has a complexity of O(log y) where y is the exponent. Since the exponentiation is by a fixed number (mod - 2 for the inversion and x - 1 for multiplying by 2), these operations can be considered O(1) for each iteration, thus making this loop O(k).

3. The final loop, which also iterates over part of the nums list and includes modular multiplication and exponentiation. Similar to the previous loop, its complexity is O(k).

Considering that the list sick would result in the list nums of size k, and taking into account the loops, the overall time complexity of the numberOfSequence method is O(k).

Space Complexity

The space complexity is determined by the storage used by the function. The key variables are:

1. The nums list, which has k elements, leading to O(k) space.

2. The variable ans and s, which use constant space O(1).

Ignoring the space used by the precomputed fac array, which can be considered preprocessing and not part of the numberOfSequence function itself, the space complexity of the numberOfSequence method is O(k), where k is the number of elements in the sick list plus the two additional elements added.

Learn more about how to find time and space complexity quickly using problem constraints.