2954. Count the Number of Infection Sequences LeetCode Solution
In this guide, you will get 2954. Count the Number of Infection Sequences LeetCode Solution with the best time and space complexity. The solution to Count the Number of Infection Sequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count the Number of Infection Sequences
You are given an integer n and an array sick sorted in increasing order, representing positions of infected people in a line of n people.
At each step, one uninfected person adjacent to an infected person gets infected. This process continues until everyone is infected.
An infection sequence is the order in which uninfected people become infected, excluding those initially infected.
Return the number of different infection sequences possible, modulo 109+7.
Example 1:
Input: n = 5, sick = [0,4]
Output: 4
Explanation:
There is a total of 6 different sequences overall.
Valid infection sequences are [1,2,3], [1,3,2], [3,2,1] and [3,1,2].
[2,3,1] and [2,1,3] are not valid infection sequences because the person at index 2 cannot be infected at the first step.
Example 2:
Input: n = 4, sick = [1]
Output: 3
Explanation:
There is a total of 6 different sequences overall.
Valid infection sequences are [0,2,3], [2,0,3] and [2,3,0].
[3,2,0], [3,0,2], and [0,3,2] are not valid infection sequences because the infection starts at the person at index 1, then the order of infection is 2, then 3, and hence 3 cannot be infected earlier than 2.
2 <= n <= 105
1 <= sick.length <= n – 1
0 <= sick[i] <= n – 1
sick is sorted in increasing order.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2954. Count the Number of Infection Sequences LeetCode Solution in C++
class Solution {
public:
int numberOfSequence(int n, vector<int>& sick) {
const auto [fact, invFact] = getFactAndInvFact(n - sick.size());
long ans = fact[n - sick.size()]; // the number of infected children
int prevSick = -1;
for (int i = 0; i < sick.size(); ++i) {
// The segment [prevSick + 1, sick - 1] are the current non-infected
// children.
const int nonInfected = sick[i] - prevSick - 1;
prevSick = sick[i];
if (nonInfected == 0)
continue;
ans *= invFact[nonInfected];
ans %= kMod;
if (i > 0) {
// There're two choices per second since the children at the two
// endpoints can both be the infect candidates. So, there are
// 2^{nonInfected - 1} ways to infect all children in the current
// segment.
ans *= modPow(2, nonInfected - 1);
ans %= kMod;
}
}
const int nonInfected = n - sick.back() - 1;
ans *= invFact[nonInfected];
return ans % kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
pair<vector<long>, vector<long>> getFactAndInvFact(int n) {
vector<long> fact(n + 1);
vector<long> invFact(n + 1);
vector<long> inv(n + 1);
fact[0] = invFact[0] = 1;
inv[0] = inv[1] = 1;
for (int i = 1; i <= n; ++i) {
if (i >= 2)
inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
fact[i] = fact[i - 1] * i % kMod;
invFact[i] = invFact[i - 1] * inv[i] % kMod;
}
return {fact, invFact};
}
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
}; /* code provided by PROGIEZ */
2954. Count the Number of Infection Sequences LeetCode Solution in Java
class Solution {
public int numberOfSequence(int n, int[] sick) {
final long[][] factAndInvFact = getFactAndInvFact(n - sick.length);
final long[] fact = factAndInvFact[0];
final long[] invFact = factAndInvFact[1];
long ans = fact[n - sick.length]; // the number of infected children
int prevSick = -1;
for (int i = 0; i < sick.length; ++i) {
// The segment [prevSick + 1, sick - 1] are the current non-infected
// children.
final int nonInfected = sick[i] - prevSick - 1;
prevSick = sick[i];
if (nonInfected == 0)
continue;
ans *= invFact[nonInfected];
ans %= kMod;
if (i > 0) {
// There're two choices per second since the children at the two
// endpoints can both be the infect candidates. So, there are
// 2^{nonInfected - 1} ways to infect all children in the current
// segment.
ans *= modPow(2, nonInfected - 1);
ans %= kMod;
}
}
final int nonInfected = n - sick[sick.length - 1] - 1;
ans *= invFact[nonInfected];
return (int) (ans % kMod);
}
private static final int kMod = 1_000_000_007;
private long[][] getFactAndInvFact(int n) {
long[] fact = new long[n + 1];
long[] invFact = new long[n + 1];
long[] inv = new long[n + 1];
fact[0] = invFact[0] = 1;
inv[0] = inv[1] = 1;
for (int i = 1; i <= n; ++i) {
if (i >= 2)
inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
fact[i] = fact[i - 1] * i % kMod;
invFact[i] = invFact[i - 1] * inv[i] % kMod;
}
return new long[][] {fact, invFact};
}
private long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
} // code provided by PROGIEZ
2954. Count the Number of Infection Sequences LeetCode Solution in Python
class Solution:
def numberOfSequence(self, n: int, sick: list[int]) -> int:
kMod = 1_000_000_007
@functools.lru_cache(None)
def fact(i: int) -> int:
return 1 if i <= 1 else i * fact(i - 1) % kMod
@functools.lru_cache(None)
def inv(i: int) -> int:
return pow(i, kMod - 2, kMod)
ans = fact(n - len(sick)) # the number of infected children
prevSick = -1
for i, s in enumerate(sick):
# The segment [prevSick + 1, sick - 1] are the current non-infected
# children.
nonInfected = sick[i] - prevSick - 1
prevSick = sick[i]
if nonInfected == 0:
continue
ans *= inv(fact(nonInfected))
ans %= kMod
if i > 0:
# There're two choices per second since the children at the two
# endpoints can both be the infect candidates. So, there are
# 2^[nonInfected - 1] ways to infect all children in the current
# segment.
ans *= pow(2, nonInfected - 1, kMod)
nonInfected = n - sick[-1] - 1
return ans * inv(fact(nonInfected)) % kMod # code by PROGIEZ
