Number of People Aware of a Secret
Understanding the Problem
We are simulating the spread of a secret over n days. One person discovers the secret on day 1. After a delay period, they start sharing it with one new person each day. After forget days, they forget the secret entirely and stop sharing.
Every new person who learns the secret follows the same rules: they wait delay days before sharing, and they forget after forget days. This creates a cascading effect where each group of knowers spawns the next, while earlier groups eventually drop off.
The core mechanic is the interplay between the sharing window and the forgetting window. A person who discovers the secret on day d can share it from day d + delay through day d + forget - 1. On day d + forget, they have already forgotten. We need to count how many people still know the secret on day n.
The structure to exploit is that everyone who discovers the secret on the same day behaves identically. So instead of tracking individual people, we can track how many new people discover the secret on each day, then sum up everyone who discovered it recently enough to still remember.
Key Constraints:
2 <= n <= 1000--> The bound is small, so even an O(n^2) day-by-day sum (about 10^6 operations) runs comfortably. An O(n) solution exists and is the target here.1 <= delay < forget <= n--> Sincedelay < forget, every person has at least one day to share the secret before forgetting, so the spread never stalls.
Approach 1: Dynamic Programming (Day-by-Day DP)
Intuition
We do not need to track individual people. Define dp[i] as the number of people who discover the secret on day i. Everyone who discovers the secret on the same day has the same sharing and forgetting schedule, so grouping by discovery day avoids the redundancy of tracking each person separately.
A person who discovers the secret on day j will share it on days j + delay, j + delay + 1, ..., j + forget - 1. On each of those days, they create exactly one new person. So the number of new people on day i is the sum of dp[j] for all j where j + delay <= i and j + forget - 1 >= i (equivalently, i - forget + 1 <= j <= i - delay).
This gives us: dp[i] = sum of dp[j] for j in [i - forget + 1, i - delay].
At the end, the answer is the sum of dp[j] for all j where j + forget > n (people who haven't forgotten by day n).
A person from day j is sharing on day i if and only if j + delay <= i (they have waited long enough) and j + forget > i (they have not forgotten yet). Each such person creates exactly one new person on day i, so the count of day-i discoverers equals the number of sharers, which is sum of dp[j] over the range [i - forget + 1, i - delay]. This collapses exponentially many individuals into at most n groups while preserving the exact count.
Algorithm
- Create an array
dpof sizen + 1, initialized to 0. - Set
dp[1] = 1(one person discovers the secret on day 1). - For each day
ifrom 2 to n: - Sum up
dp[j]for alljfrommax(1, i - forget + 1)toi - delay. - Set
dp[i]to this sum (modulo 10^9 + 7). - Sum up
dp[j]for alljwherej + forget > nto get the final answer. - Return this sum modulo 10^9 + 7.
Visualization and Code
Loading animation...
- Time Complexity: O(n * (forget - delay)). For each of the n days, we sum over a window of size at most forget - delay. In the worst case where forget is close to n, this becomes O(n^2).
- Space Complexity: O(n). We store one value per day in the dp array.
Adjacent days have overlapping summation ranges that differ by at most two elements. The next approach maintains a running sum of the sharing window and updates it incrementally instead of re-summing the window each day.
Approach 2: Optimized DP with Prefix Sum
Intuition
The inner loop in Approach 1 computes a range sum: dp[i] = sum of dp[j] for j in [i - forget + 1, i - delay]. Adjacent windows overlap heavily, so we can maintain the sum incrementally instead of recomputing it. Track a running share variable that holds how many people are actively sharing on the current day.
When we process day i, the sharing window shifts by one compared to day i - 1:
- One new group enters the sharing window: the people from day
i - delay(their delay period just ended, so they begin sharing on dayi). - One group exits the sharing window: the people from day
i - forget(they forget on dayiand stop sharing).
So we update the running sum with share += dp[i - delay] (new sharers enter) and share -= dp[i - forget] (old sharers exit), then set dp[i] = share. This computes dp[i] in O(1) per day.
Each day the sharing window shifts right by one position. The entrant at day i - delay is the group whose delay period just ended; the group at day i - forget just forgot. Adding the entrant and subtracting the leaver keeps share equal to the Approach 1 range sum without re-summing the window. One detail with the modulo: after subtracting dp[i - forget], share could go negative, so add MOD before taking the remainder.
Algorithm
- Create an array
dpof sizen + 1, initialized to 0. Setdp[1] = 1. - Maintain a variable
share = 0representing how many people are actively sharing today. - For each day
ifrom 2 to n: - If
i - delay >= 1, adddp[i - delay]toshare(people from dayi - delayjust entered their sharing window). - If
i - forget >= 1, subtractdp[i - forget]fromshare(people from dayi - forgetjust forgot). - Set
dp[i] = share. - Sum
dp[j]for alljwherej + forget > nto get the final answer. - Return the answer modulo 10^9 + 7.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We iterate through days 2 to n exactly once, doing O(1) work per day. The final summation is also O(n).
- Space Complexity: O(n). We store the dp array of size n + 1.