# Number of People Aware of a Secret
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-people-aware-of-a-secret)
Canonical: https://scaleengineer.com/dsa/problems/number-of-people-aware-of-a-secret
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Queue
**Companies:** [NCR](https://scaleengineer.com/companies/ncr), [Arcesium](https://scaleengineer.com/companies/arcesium)
---
## Problem
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** `109 + 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
## Naive Dynamic Programming
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.
**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.
**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.
### Explanation
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`.

```java
class Solution {
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        long[] dp = new long[n + 1];
        long MOD = 1_000_000_007;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            long newPeopleToday = 0;
            for (int j = i - delay; j >= Math.max(1, i - forget + 1); j--) {
                newPeopleToday = (newPeopleToday + dp[j]) % MOD;
            }
            dp[i] = newPeopleToday;
        }

        long totalKnown = 0;
        for (int i = n - forget + 1; i <= n; i++) {
            totalKnown = (totalKnown + dp[i]) % MOD;
        }

        return (int) totalKnown;
    }
}
```
### 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`.

## Optimized Dynamic Programming with Sliding Window
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.
**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.
**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).
### Explanation
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`.

```java
class Solution {
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        long[] dp = new long[n + 1]; // dp[i]: number of people who found secret on day i
        long MOD = 1_000_000_007;
        dp[1] = 1;
        
        long sharingCount = 0; // Number of people who can share the secret
        
        for (int i = 2; i <= n; i++) {
            // Add people who start sharing today (learned delay days ago)
            if (i - delay >= 1) {
                sharingCount = (sharingCount + dp[i - delay]) % MOD;
            }
            // Remove people who forget the secret today (learned forget days ago)
            if (i - forget >= 1) {
                sharingCount = (sharingCount - dp[i - forget] + MOD) % MOD;
            }
            dp[i] = sharingCount;
        }
        
        long totalKnown = 0;
        // People who found secret on day i will forget on day i + forget.
        // They know the secret on day n if i + forget > n, which means i > n - forget.
        for (int i = n - forget + 1; i <= n; i++) {
            totalKnown = (totalKnown + dp[i]) % MOD;
        }
        
        return (int) totalKnown;
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int peopleAwareOfSecret(int n, int delay, int forget) {
    int m = (n << 1) + 10;
    long[] d = new long[m];
    long[] cnt = new long[m];
    cnt[1] = 1;
    for (int i = 1; i <= n; ++i) {
      if (cnt[i] > 0) {
        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;
        }
      }
    }
    long ans = 0;
    for (int i = 1; i <= n; ++i) {
      ans = (ans + d[i]) % MOD;
    }
    return (int)ans;
  }
}

```

### Python

```python
class Solution:
    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

```

### CPP

```cpp
using 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 ; } };
```