2954. Count the Number of Infection Sequences

Description

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.

 

Constraints:

• 2 <= n <= 105
• 1 <= sick.length <= n - 1
• 0 <= sick[i] <= n - 1
• sick is sorted in increasing order.

 

Solutions

Solution: Combinatorics

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

const MODULO = BigInt(10 ** 9 + 7);
const MAX_LEN = 10 ** 5;
const inv = Array.from({ length: MAX_LEN + 1 }, () => 1n);
const fact = Array.from({ length: MAX_LEN + 1 }, () => 1n);
const invFact = Array.from({ length: MAX_LEN + 1 }, () => 1n);

for (let num = 2; num <= MAX_LEN; num++) {
  const value = BigInt(num);
  const multiple = MODULO / value;
  const remainder = Number(MODULO % value);

  inv[num] = MODULO - ((multiple * inv[remainder]) % MODULO);
}

for (let num = 2; num <= MAX_LEN; num++) {
  const value = BigInt(num);

  fact[num] = (fact[num - 1] * value) % MODULO;
  invFact[num] = (invFact[num - 1] * inv[num]) % MODULO;
}

/**
 * @param {number} n
 * @param {number[]} sick
 * @return {number}
 */
const numberOfSequence = function (n, sick) {
  const uninfectedPersons = n - sick.length;
  let prevSick = -1;
  let result = fact[uninfectedPersons];

  for (const index of sick) {
    const uninfected = index - prevSick - 1;

    result = (result * invFact[uninfected]) % MODULO;

    if (uninfected && prevSick > -1) {
      result = (result * modPow(2, uninfected - 1, MODULO)) % MODULO;
    }

    prevSick = index;
  }

  result = (result * invFact[n - prevSick - 1]) % MODULO;

  return Number(result);
};

function modPow(base, exp, mod) {
  let result = 1n;

  base = BigInt(base);
  exp = BigInt(exp);

  while (exp) {
    if (exp % 2n) {
      result = (result * base) % mod;
    }

    base = (base * base) % mod;
    exp /= 2n;
  }

  return result;
}