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:
- The infected children effectively split the queue into segments of uninfected children.
- Each segment has a number of children who will get sick in a certain number of ways.
- 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.
mod = 10**9 + 7
mx = 10**5
fac = [1] * (mx + 1)
for i in range(2, mx + 1):
fac[i] = fac[i - 1] * i % mod
class Solution:
def numberOfSequence(self, n: int, sick: List[int]) -> int:
# Calculate the number of children in each segment
nums = [b - a - 1 for a, b in pairwise([-1] + sick + [n])]
# Start with the factorial of the total count of uninfected children
s = sum(nums)
ans = fac[s]
# Divide by the factorial of the count in each segment
for x in nums:
if x:
ans = ans * pow(fac[x], mod - 2, mod) % mod
# Multiply by 2^(count-1) for non-border segments
for x in nums[1:-1]:
if x > 1:
ans = ans * pow(2, x - 1, mod) % mod
# Return the final result
return ans
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
H I H H I H H
Using the given approach:
-
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.
-
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. -
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!)
. -
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, providing2^(2-1)
different ways. -
Using Modular Arithmetic: Given the constraint of modulo
10^9 + 7
, we work within this space to find5!
modulo10^9 + 7
,1!
modulo10^9 + 7
, and2!
modulo10^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 to10^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!
is1
and of2!
is1 / 𝑓𝑎𝑐[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 inanswer * pow(2, 1, mod)
.
Plugging the numbers in:
Initial answer = fac[5] = 120 Corrected answer = 120 * modinv(fac[1]) * modinv(fac[2]) * modinv(fac[2]) (mod 10^9 + 7) Corrected answer for non-border segment = 120 * 1 * 1/2 * 1/2 * 2 (mod 10^9 + 7) Final 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:
-
The list comprehension that creates
nums
with the complexityO(k)
, wherek
is the number of elements insick
plus 2, for the additional elements added (-1
andn
). -
The loop iterating over
nums
to calculateans
. In the worst case, it iteratesk-2
times (sincenums
was created fromsick
with two additional elements). Each iteration involves a modular multiplication and a modular exponentiation. Modular exponentiation has a complexity ofO(log y)
wherey
is the exponent. Since the exponentiation is by a fixed number (mod - 2
for the inversion andx - 1
for multiplying by 2), these operations can be consideredO(1)
for each iteration, thus making this loopO(k)
. -
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 isO(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:
-
The
nums
list, which hask
elements, leading toO(k)
space. -
The variable
ans
ands
, which use constant spaceO(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.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!