2327. Number of People Aware of a Secret

This is a Dynamic Programming problem that focuses on “states” and “time intervals.” It simulates a growth process where individuals go through different phases: a delay period, a spreading period, and finally, a forgetting phase.

This problem evaluates your ability to manage a sliding window of active “spreaders” and handle modular arithmetic for large numbers.

Problem

On day 1, one person discovers a secret. You are given three integers:

1. delay: A person starts sharing the secret delay days after they discovered it.
2. forget: A person forgets the secret forget days after they discovered it.
3. n: The total number of days.

Your task: Return the number of people who know the secret at the end of day n. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1

Input: n = 6, delay = 2, forget = 4 Output: 5 Explanation:

• Day 1: 1 person knows (Person A).
• Day 2: 1 person knows (A).
• Day 3: A starts sharing. A tells 1 new person (B). Total: 2.
• Day 4: A tells 1 new person (C). B is still in delay. Total: 3.
• Day 5: A forgets. B starts sharing. B tells 1 new person (D). C starts sharing. C tells 1 new person (E). Total: 4.
• Day 6: … and so on.

Solution

The most efficient way to track this is to use a DP array where dp[i] represents the number of new people who discover the secret on day i.

Key Idea: Tracking the Spreading Population

At any day i, the number of people who can share the secret is the sum of people who discovered it between i - forget + 1 and i - delay. However, rather than re-summing every time, we can maintain a running variable sharing that adds people who just finished their delay and subtracts people who just forgot.

Algorithm Outline

1. Initialize dp array of size n + 1 with 0s. Set dp[1] = 1.
2. Initialize sharing = 0 (people currently in their “active” spreading phase).
3. Loop from day = 2 to n:
   • New Spreaders: Add people who discovered the secret delay days ago: sharing += dp[day - delay].
   • Forgetters: Remove people who discovered the secret forget days ago: sharing -= dp[day - forget].
   • New Discoveries: The number of new people on current day is exactly sharing. Set dp[day] = sharing.
4. Final Count: To find everyone who still knows the secret at day n, sum up all dp[i] from i = n - forget + 1 to n.
5. Apply modulo at every addition step to prevent overflow.

Sample Implementation (Python)

Complexity

• Time: O(n). We iterate through the days once.
• Space: O(n) to store the DP array.