Number of People Aware of a Secret

Med

#2120Time: O(n * (forget - delay)). The outer loop runs `n` times. The inner loop runs `forget - delay` times. In the worst case, `forget - delay` can be close to `n`, leading to O(n^2) complexity.Space: O(n) to store the `dp` array.2 companies

Patterns

Dynamic Programming

Data structures

Queue

Companies

NCR Arcesium

Prompt

On day 1, one person discovers a secret.

You are given an integer delay, which means that each person will share the secret with a new person every day, starting from delay days after discovering the secret. You are also given an integer forget, which means that each person will forget the secret forget days after discovering it. A person cannot share the secret on the same day they forgot it, or on any day afterwards.

Given an integer n, return the number of people who know the secret at the end of day n. Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 6, delay = 2, forget = 4
Output: 5
Explanation:
Day 1: Suppose the first person is named A. (1 person)
Day 2: A is the only person who knows the secret. (1 person)
Day 3: A shares the secret with a new person, B. (2 people)
Day 4: A shares the secret with a new person, C. (3 people)
Day 5: A forgets the secret, and B shares the secret with a new person, D. (3 people)
Day 6: B shares the secret with E, and C shares the secret with F. (5 people)

Example 2:

Input: n = 4, delay = 1, forget = 3
Output: 6
Explanation:
Day 1: The first person is named A. (1 person)
Day 2: A shares the secret with B. (2 people)
Day 3: A and B share the secret with 2 new people, C and D. (4 people)
Day 4: A forgets the secret. B, C, and D share the secret with 3 new people. (6 people)

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem by simulating the process day by day. We define dp[i] as the number of new people who learn the secret on day i. We build this dp array from day 1 to day n by iterating through all previous days to see who can share the secret.

Algorithm

Initialize MOD = 10^9 + 7.
Create a dp array of size n + 1, where dp[i] will store the number of people who learn the secret on day i.
Set the base case: dp[1] = 1.
Iterate with a variable i from 2 to n to represent the current day:
- For each day i, calculate the number of new people who learn the secret. These are the people who can share today.
- A person who learned on day j can share on day i if delay <= i - j < forget.
- This is equivalent to i - forget < j <= i - delay.
- Iterate with a variable j from i - delay down to i - forget + 1.
- Sum up dp[j] for all valid j (i.e., j >= 1) to get the number of new people for day i.
- Store this sum in dp[i], taking the result modulo MOD.
After filling the dp array, calculate the total number of people who know the secret on day n.
A person who learned on day j still knows the secret on day n if they haven't forgotten it yet, which means j + forget > n, or j > n - forget.
Sum up dp[j] for j from n - forget + 1 to n.
Return this final sum modulo MOD.

Walkthrough

We create a dp array of size n+1, where dp[i] stores the number of people who discover the secret on day i. The base case is dp[1] = 1, as one person discovers the secret on day 1. For each day i from 2 to n, we calculate dp[i]. The number of new people on day i is the sum of people who are able to share the secret. A person who learned the secret on day j can share it on day i if they have known it for at least delay days but less than forget days. This condition is delay <= i - j < forget. Rearranging the inequality, we get i - forget < j <= i - delay. So, to find dp[i], we sum up dp[j] for all j in this range. All additions are performed modulo 10^9 + 7. After computing the dp array up to n, the total number of people who know the secret on day n is the sum of all people who learned it on some day j and have not yet forgotten it. A person who learned on day j forgets on day j + forget. They still know the secret on day n if n < j + forget, which means j > n - forget. Therefore, the final answer is the sum of dp[j] for j from n - forget + 1 to n.

1class Solution {2    public int peopleAwareOfSecret(int n, int delay, int forget) {3        long[] dp = new long[n + 1];4        long MOD = 1_000_000_007;5        dp[1] = 1;6 7        for (int i = 2; i <= n; i++) {8            long newPeopleToday = 0;9            for (int j = i - delay; j >= Math.max(1, i - forget + 1); j--) {10                newPeopleToday = (newPeopleToday + dp[j]) % MOD;11            }12            dp[i] = newPeopleToday;13        }14 15        long totalKnown = 0;16        for (int i = n - forget + 1; i <= n; i++) {17            totalKnown = (totalKnown + dp[i]) % MOD;18        }19 20        return (int) totalKnown;21    }22}

Complexity

Time

O(n * (forget - delay)). The outer loop runs `n` times. The inner loop runs `forget - delay` times. In the worst case, `forget - delay` can be close to `n`, leading to O(n^2) complexity.

Space

O(n) to store the `dp` array.

Trade-offs

Pros

Conceptually straightforward, directly translating the problem's day-by-day simulation.
Easy to implement without complex data structures.

Cons

Inefficient for larger values of n and forget - delay, leading to a quadratic time complexity.
May result in 'Time Limit Exceeded' on platforms with strict time limits.

This approach improves upon the naive DP by recognizing that the sum calculation for dp[i] is over a sliding window. Instead of re-calculating the sum each time, we can maintain a running count of people who are eligible to share the secret, updating it in constant time for each day.

Algorithm

Initialize MOD = 10^9 + 7.
Create a dp array of size n + 1 where dp[i] stores the number of people who learn the secret on day i.
Set dp[1] = 1.
Initialize a variable sharingCount = 0. This will maintain the number of people who are currently able to share the secret.
Iterate i from 2 to n:
- Update sharingCount based on who starts and stops sharing relative to day i.
- People who learned on day i - delay start sharing today. If i - delay >= 1, add dp[i - delay] to sharingCount.
- People who learned on day i - forget forget the secret today and stop sharing. If i - forget >= 1, subtract dp[i - forget] from sharingCount.
- Perform all calculations modulo MOD, ensuring to handle potential negative results from subtraction by adding MOD before the modulo operation.
- The number of new people on day i is the current sharingCount. Set dp[i] = sharingCount.
After the loop, calculate the total number of people who know the secret on day n.
Sum dp[j] for j from n - forget + 1 to n.
Return the final sum.

Walkthrough

We still use a dp array where dp[i] is the number of people who learn the secret on day i. We introduce a variable, sharingCount, to keep track of the number of people who can share the secret on the current day. The number of new people on day i, dp[i], is simply equal to this sharingCount. We iterate from day 2 to n. For each day i, we update sharingCount. The people who learned the secret on day i - delay now become eligible to share, so we add dp[i - delay] to sharingCount. Simultaneously, people who learned the secret on day i - forget will forget it today and can no longer share, so we subtract dp[i - forget] from sharingCount. This way, sharingCount is updated in O(1) time for each day. The base case is dp[1] = 1. The final answer is calculated in the same way as the naive approach: by summing up dp[j] for j from n - forget + 1 to n.

1class Solution {2    public int peopleAwareOfSecret(int n, int delay, int forget) {3        long[] dp = new long[n + 1]; // dp[i]: number of people who found secret on day i4        long MOD = 1_000_000_007;5        dp[1] = 1;6        7        long sharingCount = 0; // Number of people who can share the secret8        9        for (int i = 2; i <= n; i++) {10            // Add people who start sharing today (learned delay days ago)11            if (i - delay >= 1) {12                sharingCount = (sharingCount + dp[i - delay]) % MOD;13            }14            // Remove people who forget the secret today (learned forget days ago)15            if (i - forget >= 1) {16                sharingCount = (sharingCount - dp[i - forget] + MOD) % MOD;17            }18            dp[i] = sharingCount;19        }20        21        long totalKnown = 0;22        // People who found secret on day i will forget on day i + forget.23        // They know the secret on day n if i + forget > n, which means i > n - forget.24        for (int i = n - forget + 1; i <= n; i++) {25            totalKnown = (totalKnown + dp[i]) % MOD;26        }27        28        return (int) totalKnown;29    }30}

Complexity

Time

O(n). The main loop runs `n` times, and each step inside the loop takes constant time. The final summation takes O(forget), which is at most O(n).

Space

O(n) to store the `dp` array. This can be further optimized to O(forget) since we only need to look back `forget` days.

Trade-offs

Pros

Highly efficient with linear time complexity, making it suitable for the given constraints and beyond.
Reduces redundant calculations by maintaining a running sum (sliding window).

Cons

Slightly more complex to reason about compared to the naive approach.
Still requires linear space proportional to n, which could be a limitation for extremely large n (though not an issue with the problem's constraints).

Solutions

Solution

1class Solution {2private3  static final int MOD = (int)1 e9 + 7;4public5  int peopleAwareOfSecret(int n, int delay, int forget) {6    int m = (n << 1) + 10;7    long[] d = new long[m];8    long[] cnt = new long[m];9    cnt[1] = 1;10    for (int i = 1; i <= n; ++i) {11      if (cnt[i] > 0) {12        d[i] = (d[i] + cnt[i]) % MOD;13        d[i + forget] = (d[i + forget] - cnt[i] + MOD) % MOD;14        int nxt = i + delay;15        while (nxt < i + forget) {16          cnt[nxt] = (cnt[nxt] + cnt[i]) % MOD;17          ++nxt;18        }19      }20    }21    long ans = 0;22    for (int i = 1; i <= n; ++i) {23      ans = (ans + d[i]) % MOD;24    }25    return (int)ans;26  }27}

1class Solution:2    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int: m = (n << 1) + 10 d = [0] * m cnt = [0] * m cnt[1] = 1 for i in range(1, n + 1): if cnt[i]: d[i] += cnt[i] d[i + forget] -= cnt[i] nxt = i + delay while nxt < i + forget: cnt[nxt] += cnt[i] nxt += 1 mod = 10 ** 9 + 7 return sum(d[: n + 1]) % mod

1using ll = long long ; const int mod = 1e9 + 7 ; class Solution { public: int peopleAwareOfSecret ( int n , int delay , int forget ) { int m = ( n << 1 ) + 10 ; vector < ll > d ( m ); vector < ll > cnt ( m ); cnt [ 1 ] = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { if ( ! cnt [ i ]) continue ; d [ i ] = ( d [ i ] + cnt [ i ]) % mod ; d [ i + forget ] = ( d [ i + forget ] - cnt [ i ] + mod ) % mod ; int nxt = i + delay ; while ( nxt < i + forget ) { cnt [ nxt ] = ( cnt [ nxt ] + cnt [ i ]) % mod ; ++ nxt ; } } int ans = 0 ; for ( int i = 1 ; i <= n ; ++ i ) ans = ( ans + d [ i ]) % mod ; return ans ; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem