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

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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

1# Constants for modulus and maximum values
2MOD = 10**9 + 7
3MAX = 10**5
4
5# Precompute factorials modulo MOD
6factorials = [1] * (MAX + 1)
7for i in range(2, MAX + 1):
8    factorials[i] = factorials[i - 1] * i % MOD
9
10class Solution:
11    def numberOfSequence(self, n: int, sick: List[int]) -> int:
12        # Calculate the number of healthy people between each pair of sick individuals,
13        # including before the first sick and after the last sick person
14        healthy_intervals = [b - a - 1 for a, b in zip([-1] + sick, sick + [n])]
15
16        # Start with the number of permutations of the total number of healthy people
17        answer = factorials[sum(healthy_intervals)]
18
19        # Divide by the factorial of each interval to remove cases where healthy people are indistinguishable
20        for interval in healthy_intervals:
21            if interval:
22                answer = answer * pow(factorials[interval], MOD - 2, MOD) % MOD
23
24        # For internal intervals (not the first or last), every healthy individual has 
25        # two choices (to stay home or not), which is 2^(x-1) since the first choice is fixed
26        # to prevent adjacent sick people from being in the same partition
27        for interval in healthy_intervals[1:-1]:
28            if interval > 1:
29                answer = answer * pow(2, interval - 1, MOD) % MOD
30
31        # Return the total number of valid sequences
32        return answer
33
1class Solution {
2    // Define the modulus constant for mathematical operations to keep the result within integer limits.
3    private static final int MOD = (int) (1e9 + 7);
4    // Define the maximum number supported for factorial calculation.
5    private static final int MAX = 100000;
6    // Pre-compute factorials up to MAX and store them in an array.
7    private static final int[] factorials = new int[MAX + 1];
8
9    // Static initializer block to fill the factorials array.
10    static {
11        factorials[0] = 1;
12        for (int i = 1; i <= MAX; i++) {
13            // Calculate i factorial modulo MOD and store it in factorials array.
14            factorials[i] = (int) ((long) factorials[i - 1] * i % MOD);
15        }
16    }
17
18    // Function to calculate the number of valid sequences given sick persons' positions and total number of people.
19    public int numberOfSequence(int n, int[] sick) {
20        int sickCount = sick.length;
21        int[] distances = new int[sickCount + 1];
22        // Distance from the start to the first sick person.
23        distances[0] = sick[0];
24        // Distance from the last sick person to the end.
25        distances[sickCount] = n - sick[sickCount - 1] - 1;
26
27        // Calculate the distances between consecutive sick people.
28        for (int i = 1; i < sickCount; i++) {
29            distances[i] = sick[i] - sick[i - 1] - 1;
30        }
31
32        // Sum of all distances (number of healthy people).
33        int sumDistances = 0;
34        for (int x : distances) {
35            sumDistances += x;
36        }
37
38        // Calculate the initial answer as factorial of sum of all distances.
39        int result = factorials[sumDistances];
40        // For each non-zero distance, multiply the result with the modular inverse of its factorial.
41        for (int x : distances) {
42            if (x > 0) {
43                result = (int) ((long) result * modularPow(factorials[x], MOD - 2) % MOD);
44            }
45        }
46
47        // For each distance except the first and last, multiply the result with powers of 2.
48        for (int i = 1; i < distances.length - 1; ++i) {
49            if (distances[i] > 1) {
50                result = (int) ((long) result * modularPow(2, distances[i] - 1) % MOD);
51            }
52        }
53        return result;
54    }
55
56    // Function to calculate a^b mod MOD using fast exponentiation.
57    private int modularPow(long base, long exponent) {
58        long result = 1;
59        for (; exponent > 0; exponent >>= 1) {
60            // If the current exponent bit is 1, multiply result with base.
61            if ((exponent & 1) == 1) {
62                result = result * base % MOD;
63            }
64            // Square the base for the next iteration.
65            base = base * base % MOD;
66        }
67        return (int) result;
68    }
69}
70
1#include <vector>
2#include <numeric>
3
4const int MAX_VALUE = 1e5;    // Max size for factorial array
5const int MOD = 1e9 + 7;      // Modulus value for calculations
6int factorial[MAX_VALUE + 1];  // Array to store precomputed factorials
7
8// Anonymous namespace to avoid pollution of the global namespace
9namespace {
10    // Lambda function for initialization, executed once
11    auto initializer = [] {
12        factorial[0] = 1; // 0! is 1 by definition
13        // Pre-compute factorials modulo MOD
14        for (int i = 1; i <= MAX_VALUE; ++i) {
15            factorial[i] = (static_cast<long long>(factorial[i - 1]) * i) % MOD;
16        }
17        return 0; // Dummy value to satisfy lambda, not used
18    }();
19
20    // Computes a^b % MOD using binary exponentiation
21    int QuickPower(long long base, long long exponent) {
22        long long result = 1;
23        while(exponent > 0) {
24            if (exponent & 1) { // If exponent is odd, multiply result by the current base
25                result = (result * base) % MOD;
26            }
27            base = (base * base) % MOD; // Square the base
28            exponent >>= 1; // Divide exponent by 2
29        }
30        return result;
31    }
32} // End of anonymous namespace
33
34class Solution {
35public:
36    int NumberOfSequence(int n, std::vector<int>& sick) {
37        int m = sick.size();
38        std::vector<int> gaps(m + 1);
39
40        // Calculate the number of healthy individuals at the start
41        gaps[0] = sick[0];
42        // Calculate the number of healthy individuals at the end
43        gaps[m] = n - sick[m - 1] - 1;
44        // Calculate the number of healthy individuals between sick individuals
45        for (int i = 1; i < m; i++) {
46            gaps[i] = sick[i] - sick[i - 1] - 1;
47        }
48
49        // Sum the gaps (total number of healthy individuals)
50        int totalHealthy = std::accumulate(gaps.begin(), gaps.end(), 0);
51        // Start with factorial of total number of healthy individuals
52        long long answer = factorial[totalHealthy];
53
54        // Divide by the factorial of healthy individuals in each gap
55        for (int count : gaps) {
56            if (count > 0) {
57                answer = answer * QuickPower(factorial[count], MOD - 2) % MOD;
58            }
59        }
60
61        // Multiply by 2^(gap_size - 1) for each gap that has more than 1 individual
62        for (int i = 1; i < gaps.size() - 1; ++i) {
63            if (gaps[i] > 1) {
64                answer = answer * QuickPower(2, gaps[i] - 1) % MOD;
65            }
66        }
67
68        return answer;
69    }
70};
71
1// Define constant maximum value.
2const MAX = 1e5;
3
4// Define constant MOD value as a bigint for modulo operations.
5const MOD: bigint = BigInt(1e9 + 7);
6
7// Array to store precalculated factorial values.
8const factorial: bigint[] = new Array(MAX + 1);
9
10// Self-invoking function to initialize the precalculated factorial array.
11const initialize = (() => {
12    factorial[0] = 1n; // Define factorial of 0 as 1.
13    for (let i = 1; i <= MAX; ++i) {
14        factorial[i] = (factorial[i - 1] * BigInt(i)) % MOD;
15    }
16})();
17
18/**
19 * Fast exponentiation function to raise a to the power n mod MOD.
20 *
21 * @param a - The base as a bigint.
22 * @param n - The exponent as an integer.
23 * @returns The result of a^n mod MOD as a bigint.
24 */
25function quickPow(a: bigint, n: number): bigint {
26    let result = 1n;
27    while (n > 0) {
28        if (n & 1) {
29            result = (result * a) % MOD;
30        }
31        a = (a * a) % MOD;
32        n >>= 1;
33    }
34    return result;
35}
36
37/**
38 * Function to calculate the number of valid sequences given the constraints.
39 *
40 * @param n - Total number of people.
41 * @param sick - Array indicating positions of sick people.
42 * @returns The number of valid sequences as a number.
43 */
44function numberOfSequence(n: number, sick: number[]): number {
45    const m = sick.length;
46    const spaces: number[] = new Array(m + 1);
47    // Calculate the number of healthy people before the first sick person and after the last sick person.
48    spaces[0] = sick[0];
49    spaces[m] = n - sick[m - 1] - 1;
50    // Calculate spaces between sick people.
51    for (let i = 1; i < m; i++) {
52        spaces[i] = sick[i] - sick[i - 1] - 1;
53    }
54
55    // Sum up all spaces to get the total count of healthy people.
56    const totalHealthy = spaces.reduce((acc, x) => acc + x, 0);
57    // Start with the factorial of the total healthy count.
58    let answer = factorial[totalHealthy];
59    // Divide by the factorial of individuals for each space segments (inverse permutation).
60    for (let x of spaces) {
61        if (x > 0) {
62            answer = (answer * quickPow(factorial[x], Number(MOD) - 2)) % MOD;
63        }
64    }
65    // Multiply by 2^(x-1) for each space between sick people for permutations.
66    for (let i = 1; i < spaces.length - 1; ++i) {
67        if (spaces[i] > 1) {
68            answer = (answer * quickPow(2n, spaces[i] - 1)) % MOD;
69        }
70    }
71    return Number(answer);
72}
73

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used in a depth first search?


Recommended Readings

Got a question?Β Ask the Monster AssistantΒ anything you don't understand.

Still not clear? Ask in the Forum, Β DiscordΒ orΒ SubmitΒ the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns
←
↑πŸͺ„