2327. Number of People Aware of a Secret

This problem shows up frequently in interviews because it tests whether we can track how information spreads across days under constraints like “people begin sharing only after delay days” and “they stop contributing once forget days have passed.” To solve it efficiently, we use Dynamic Programming, tracking how many people learn the secret each day and using a sliding window to model who can currently share.

Problem statement

You’re given three integers n, delay, and forget.

On day 1, exactly one person discovers a secret.

• After someone learns the secret, they will wait delay days, then start telling exactly one new person per day.
• After forget days, they forget the secret and stop sharing forever (they cannot share on the day they forget, or any day after).

Your task is to compute how many people still know the secret at the end of day n. As the answer may be very large, return the answer in modulo 10⁹ + 7.

Constraints

• 2 <= n <= 1000
• 1 <= delay < forget <= n

Examples

Why tracking individuals is impractical

A naive approach to solving this problem is to track each person, simulate the days they can share, and recursively create new people for each share. The population grows exponentially (branching process), so this becomes exponential time and completely infeasible even for n=1000. It also repeats the same “how many people exist on day d” subcomputations many times (classic overlapping subproblems).

Optimized approach using Dynamic Programming

Instead of tracking individuals, we group people by the day they learned the secret. Let dp[d] represent the number of people who discover the secret on day d.

• A cohort that learns on day x begins sharing on day x + delay
• This same cohort stops sharing on day x + forget (when they forget)
• Between these two boundaries, each person in the cohort shares with one new person per day

On any given day d, the total number of new learners equals the number of currently active sharers. To find this, we sum across all cohorts whose sharing window includes day d, specifically, cohorts from days d - forget + 1 through d - delay.

This transforms an exponential individual-tracking problem into a linear scan over days, where each day we:

1. Calculate active sharers (the sum of recent cohorts still eligible to share)
2. Record that count as the new cohort for day d
3. Accumulate the count of people who still remember the secret

Step-by-step algorithm

1. Initialize an array dp of length n + 1 with 0.
2. Set dp[1] = 1 (one person learns on day 1).
3. Initialize share with 0. This tracks the number of people who can share on the current day.
4. For each day from 2 to n:
   1. Compute startDay = day - delay, which is the discovery day of the cohort that becomes eligible to start sharing on the current day.
   2. If startDay is greater than or equal to 1,
      1. Add dp[startDay] to share because the people who learned on startDay become eligible to start sharing today.
   3. Initiliaze forgetDay by computing day - forget.
   4. If forgetDay is greater than or equal to 1,
      1. Subtract dp[forgetDay] from share because the people who learned on forget_day forget the secret today, and can no longer share.
   5. Set dp[day] = share because each person who is eligible to share tells the secret to exactly one new person today, so the number of new learners equals the current number of active sharers.
5. Set start to the max of 1 and n - forget + 1, where n - forget + 1 is the earliest day whose learners still remember the secret on day n, and max ensures start never falls below day 1.
6. Set ans to the sum of dp[day] from start through n (the slice ends at n + 1 to include day n), then apply % MOD, where MOD = 10^9 + 7, to keep the result within the required modulus.
7. In the end, return ans.

Let’s look at the following illustration to better understand the solution.

1 / 6

Code implementation

from typing import List

MOD = 10**9 + 7

def people_aware_of_secret(n, delay, forget):
    # dp[d] = number of people who learn the secret on day d (1-indexed)
    dp = [0] * (n + 1)
    dp[1] = 1

    # share = number of people eligible to share the secret on the current day
    share = 0

    for day in range(2, n + 1):
        # People who learned on (day - delay) start sharing today
        startDay = day - delay
        if startDay >= 1:
            share = (share + dp[startDay]) % MOD

        # People who learned on (day - forget) forget today and cannot share anymore
        forgetDay = day - forget
        if forgetDay >= 1:
            share = (share - dp[forgetDay]) % MOD

        dp[day] = share  # New learners today

    # Sum all cohorts who still remember at end of day n:
    # learned on days in [n - forget + 1, n]
    start = max(1, n - forget + 1)
    ans = sum(dp[start:n + 1]) % MOD
    return ans

def main():
    tests = [
        (6, 2, 3),   # classic: should be 5
        (4, 1, 3),   # classic: should be 6
        (5, 2, 4),   # custom small
        (7, 3, 5),   # long delay, short sharing window
        (10, 1, 10), # nobody forgets within n except day 11+, near "always remember"
    ]

    for i, (n, delay, forget) in enumerate(tests, 1):
        result = people_aware_of_secret(n, delay, forget)
        print(f"{i}. \t Input: n = {n}, delay = {delay}, forget = {forget}")
        print(f" \t Output: {result}")
        print("-"*75)

if __name__ == "__main__":
    main()

Time complexity

The time complexity of this algorithm is O(n) because we iterate once from day 2 to day n, doing O(1) work per day.

Space complexity

The space complexity of this algorithm is O(n) because we store the dp array of size n+1 to later sum the cohorts that still remember on day n.

Common pitfalls and interview tips

1. Off-by-one on forgetting day: If someone forgets on day x + forget, they cannot share on that day, and they should not be counted as knowing at the end of that day.
2. Negative modulo during subtraction: In Python, share = (share - value) % MOD is safe; in other languages, where % can return a negative value, use share = (share - value + MOD) % MOD to keep the running count non-negative.
3. Wrong final counting window: The final answer is not “active sharers.” It is everyone who learned within the last forget - 1 days, i.e., days [n - forget + 1, n].