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.
- Difficulty: Medium
- Topics: Dynamic Programming, Simulation, Queue
- Asked at: Amazon, Google, Sprinklr, Arcesium
- 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 <= 10001 <= delay < forget <= n
Hints for Number of People Aware of a Secret
Hint 1
Group people by the day they learned the secret — everyone in a group behaves identically.
Hint 2
dp[i]is how many people learn it on dayi; they share on daysi + delay … i + forget - 1.Hint 3
Maintain the number of active sharers with a running sum that adds
dp[i - delay]and removesdp[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
dp[1] = 1for the original person.- For each day
i, adddp[i - delay]to the active sharer count (they start sharing today) and subtractdp[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 lastforgetdays, 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
MODbefore reducing. - The final sum runs over the last
forgetdays, not over all days. - Sharing starts
delaydays after learning, so dayi + delayis 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]) % MODJava
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