Number of People Aware of a Secret

Medium
876.

Number of People Aware of a Secret

Number of People Aware of a Secret is a medium coding problem on dynamic programming, simulation and queue, asked in Amazon, Google, Sprinklr and Arcesium interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} delay
 * @param {number} forget
 * @return {number}
 */
var peopleAwareOfSecret = function(n, delay, forget) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of People Aware of a Secret — Problem & Solution

Number of People Aware of a Secret solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of People Aware of a Secret is a medium coding problem on dynamic programming, simulation and queue, asked in Amazon, Google, Sprinklr and Arcesium interviews.

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

Hints for Number of People Aware of a Secret

  1. Hint 1

    Group people by the day they learned the secret — everyone in a group behaves identically.

  2. Hint 2

    dp[i] is how many people learn it on day i; they share on days i + delay … i + forget - 1.

  3. Hint 3

    Maintain the number of active sharers with a running sum that adds dp[i - delay] and removes dp[i - forget].

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

  1. dp[1] = 1 for the original person.
  2. 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).
  3. dp[i] equals that active count — each sharer tells exactly one new person.
  4. 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

Java

public static int peopleAwareOfSecret(int n, int delay, int forget) {
    final int MOD = 1000000007;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    int share = 0, ans = 0;
    for (int 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 (int i = Math.max(1, n - forget + 1); i <= n; i++) ans = (ans + dp[i]) % MOD;
    return ans;
}

C++

int peopleAwareOfSecret(int n, int delay, int forget) {
    const int MOD = 1000000007;
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    int share = 0, ans = 0;
    for (int 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 (int i = max(1, n - forget + 1); i <= n; i++) ans = (ans + dp[i]) % MOD;
    return ans;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Queues and Deques