Number of People Aware of a Secret

medium queue dp simulation

Problem

On day 1 a single person discovers a secret. Starting delay days after learning it, each person tells the secret to exactly one brand-new person every day — until forget days after learning it, at which point they forget it entirely and stop sharing (someone who forgot may even be told again later).

Given n, delay, and forget, return how many people still know the secret at the end of day n, modulo 10⁹ + 7.

Inputn = 6, delay = 2, forget = 4

Output5

New learners per day are 1, 0, 1, 1, 1, 2; the day-1 discoverer forgets on day 5, so 1 + 1 + 1 + 2 = 5 people still know the secret.

n (days)

delay

forget

def people_aware_of_secret(n, delay, forget):
    MOD = 10 ** 9 + 7
    dp = [0] * (n + 1)   # dp[d] = people who first learn on day d
    dp[1] = 1
    sharers = 0          # cohorts currently inside the sharing window
    for day in range(2, n + 1):
        if day - delay >= 1:
            sharers = (sharers + dp[day - delay]) % MOD   # joins queue
        if day - forget >= 1:
            sharers = (sharers - dp[day - forget]) % MOD  # forgets
        dp[day] = sharers
    return sum(dp[n - forget + 1:]) % MOD

function peopleAwareOfSecret(n, delay, forget) {
  const MOD = 1000000007;
  const dp = new Array(n + 1).fill(0); // dp[d] = new learners on day d
  dp[1] = 1;
  let sharers = 0; // cohorts currently inside the sharing window
  for (let day = 2; day <= n; day++) {
    if (day - delay >= 1) sharers = (sharers + dp[day - delay]) % MOD;
    if (day - forget >= 1) sharers = (sharers - dp[day - forget] + MOD) % MOD;
    dp[day] = sharers;
  }
  let total = 0;
  for (let d = n - forget + 1; d <= n; d++) total = (total + dp[d]) % MOD;
  return total;
}

int peopleAwareOfSecret(int n, int delay, int forget) {
    final int MOD = 1_000_000_007;
    long[] dp = new long[n + 1]; // dp[d] = new learners on day d
    dp[1] = 1;
    long sharers = 0; // cohorts currently inside the sharing window
    for (int day = 2; day <= n; day++) {
        if (day - delay >= 1) sharers = (sharers + dp[day - delay]) % MOD;
        if (day - forget >= 1) sharers = (sharers - dp[day - forget] + MOD) % MOD;
        dp[day] = sharers;
    }
    long total = 0;
    for (int d = n - forget + 1; d <= n; d++) total = (total + dp[d]) % MOD;
    return (int) total;
}

int peopleAwareOfSecret(int n, int delay, int forget) {
    const long long MOD = 1000000007;
    vector<long long> dp(n + 1, 0); // dp[d] = new learners on day d
    dp[1] = 1;
    long long sharers = 0; // cohorts currently inside the sharing window
    for (int day = 2; day <= n; day++) {
        if (day - delay >= 1) sharers = (sharers + dp[day - delay]) % MOD;
        if (day - forget >= 1) sharers = (sharers - dp[day - forget] + MOD) % MOD;
        dp[day] = sharers;
    }
    long long total = 0;
    for (int d = n - forget + 1; d <= n; d++) total = (total + dp[d]) % MOD;
    return (int) total;
}

Explanation

Tracking individual people explodes quickly, so the key insight is to group them by the day they learned the secret: dp[d] counts the people who first hear it on day d. Everyone in a cohort behaves identically — they all start telling on day d + delay and all forget on day d + forget.

That turns the problem into a sliding window that behaves exactly like a queue. On day t, the cohorts actively sharing are those that learned between day t − forget + 1 and day t − delay. Each new day, the cohort from t − delay is enqueued at the back (its delay just expired) and the cohort from t − forget is dequeued from the front (it just forgot). A running total sharers tracks the queue's population, so both updates are O(1) instead of re-summing the window.

Since every active sharer tells exactly one new person per day, the number of new learners is simply dp[t] = sharers. This is the DP recurrence, computed by simulation: one enqueue, one dequeue, one assignment per day.

Walking the default example (n = 6, delay = 2, forget = 4): day 1 gives dp[1] = 1. Day 2: no cohort has waited delay days, so dp[2] = 0. Day 3: the day-1 cohort joins the queue, dp[3] = 1. Day 4: the empty day-2 cohort joins, dp[4] = 1. Day 5: day-3's cohort joins but day-1's forgets and leaves, dp[5] = 1. Day 6: day-4's cohort joins, day-2's (empty) leaves, so two sharers give dp[6] = 2.

At the end, only people who learned within the last forget days still remember, so the answer is dp[n − forget + 1] + … + dp[n] — here 1 + 1 + 1 + 2 = 5. All arithmetic is kept modulo 10⁹ + 7 because the counts grow exponentially.

Each of the n days does constant work, giving O(n) time, and the dp table holds one number per day, giving O(n) space (a true queue of at most forget cohorts would even cut it to O(forget)).

Time: O(n) Space: O(n)