Number of People Aware of a Secret — Medium Problem & Solution

On day 1 one person learns a secret. Anyone who learns it starts sharing it with one new person per day beginning delay days later, and forgets it (and…

Difficulty: Medium
Topics: Dynamic Programming, Simulation, Queue
Asked at: Amazon, Google, Sprinklr
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

On day 1 one person learns a secret. Anyone who learns it starts sharing it with one new person per day beginning delay days later, and forgets it (and stops sharing) exactly forget days after learning it.

Return the number of people who still know the secret at the end of day n, modulo 10^9 + 7.

Example 1

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

Example 2

Input: n = 4, delay = 1, forget = 3
Output: 6

Example 3

Input: n = 2, delay = 1, forget = 2
Output: 2
Explanation: On day 2 the first person shares with one other and only forgets on day 3.

Constraints

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

How to solve Number of People Aware of a Secret

Track new learners per day. The number of people sharing on day i is a sliding window over earlier days — those who learned between i - forget + 1 and i - delay — which a running sum maintains in constant time per day.

Approach

dp[1] = 1 for the original person.
For each day i, add dp[i - delay] to the active sharer count (they start sharing today) and subtract dp[i - forget] (they forgot today).
dp[i] equals that active count — each sharer tells exactly one new person.
The answer sums dp[i] over the last forget days, since anyone earlier has already forgotten.

Why it works

Everyone who learns on the same day starts and stops sharing on the same days, so the whole population collapses to counts per learning day. A person who learned on day j is still remembering on day n exactly when n - j < forget, which is the summation range at the end.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

Subtracting before taking the modulo can go negative — add MOD before reducing.
The final sum runs over the last forget days, not over all days.
Sharing starts delay days after learning, so day i + delay is the first one.

Reference solution

Python

def peopleAwareOfSecret(n: int, delay: int, forget: int) -> int:
    MOD = 1000000007
    dp = [0] * (n + 1)
    dp[1] = 1
    share = 0
    for i in range(2, n + 1):
        if i - delay >= 1:
            share = (share + dp[i - delay]) % MOD
        if i - forget >= 1:
            share = (share - dp[i - forget]) % MOD
        dp[i] = share
    return sum(dp[max(1, n - forget + 1):n + 1]) % MOD

JavaScript

var peopleAwareOfSecret = function(n, delay, forget) {
    var MOD = 1000000007;
    var dp = [];
    for (var t = 0; t <= n; t++) dp.push(0);
    dp[1] = 1;
    var share = 0, ans = 0;
    for (var i = 2; i <= n; i++) {
        if (i - delay >= 1) share = (share + dp[i - delay]) % MOD;
        if (i - forget >= 1) share = (share - dp[i - forget] + MOD) % MOD;
        dp[i] = share;
    }
    for (var j = Math.max(1, n - forget + 1); j <= n; j++) ans = (ans + dp[j]) % MOD;
    return ans;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 195 dynamic programming problems · the whole catalogue