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 dayn. Since the answer may be very large, return it modulo `109

  • 7`.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


    
    
    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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


    
    
    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

Solution

Method 1 – Dynamic Programming Simulation

Intuition

We simulate the process day by day, tracking how many people learn the secret each day, when they start sharing, and when they forget. We use a DP array where dp[i] is the number of people who learn the secret on day i. For each person, we add their sharing to future days and subtract when they forget.

Approach

  1. Initialize dp[1] = 1 (first person knows the secret on day 1).
  2. For each day, for each person who learns the secret, add their sharing to days [day+delay, day+forget).
  3. At the end, sum all people who still know the secret (i.e., those who have not forgotten by day n).
  4. Use modulo 1e9+7 for large numbers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <vector>
using namespace std;
class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        const int MOD = 1e9+7;
        vector<int> dp(n+2, 0);
        dp[1] = 1;
        for (int day = 1; day <= n; ++day) {
            if (dp[day] == 0) continue;
            for (int d = day+delay; d < day+forget && d <= n; ++d) {
                dp[d] = (dp[d] + dp[day]) % MOD;
            }
        }
        int ans = 0;
        for (int day = n-forget+1; day <= n; ++day) {
            if (day >= 1) ans = (ans + dp[day]) % MOD;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func peopleAwareOfSecret(n, delay, forget int) int {
    mod := int(1e9+7)
    dp := make([]int, n+2)
    dp[1] = 1
    for day := 1; day <= n; day++ {
        if dp[day] == 0 { continue }
        for d := day+delay; d < day+forget && d <= n; d++ {
            dp[d] = (dp[d] + dp[day]) % mod
        }
    }
    ans := 0
    for day := n-forget+1; day <= n; day++ {
        if day >= 1 { ans = (ans + dp[day]) % mod }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        int MOD = (int)1e9+7;
        int[] dp = new int[n+2];
        dp[1] = 1;
        for (int day = 1; day <= n; ++day) {
            if (dp[day] == 0) continue;
            for (int d = day+delay; d < day+forget && d <= n; ++d) {
                dp[d] = (dp[d] + dp[day]) % MOD;
            }
        }
        int ans = 0;
        for (int day = n-forget+1; day <= n; ++day) {
            if (day >= 1) ans = (ans + dp[day]) % MOD;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun peopleAwareOfSecret(n: Int, delay: Int, forget: Int): Int {
        val MOD = 1_000_000_007
        val dp = IntArray(n+2)
        dp[1] = 1
        for (day in 1..n) {
            if (dp[day] == 0) continue
            for (d in (day+delay) until (day+forget).coerceAtMost(n+1)) {
                if (d <= n) dp[d] = (dp[d] + dp[day]) % MOD
            }
        }
        var ans = 0
        for (day in (n-forget+1)..n) {
            if (day >= 1) ans = (ans + dp[day]) % MOD
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        MOD = 10**9+7
        dp = [0]*(n+2)
        dp[1] = 1
        for day in range(1, n+1):
            if dp[day] == 0: continue
            for d in range(day+delay, min(day+forget, n+1)):
                dp[d] = (dp[d] + dp[day]) % MOD
        ans = 0
        for day in range(n-forget+1, n+1):
            if day >= 1:
                ans = (ans + dp[day]) % MOD
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn people_aware_of_secret(n: i32, delay: i32, forget: i32) -> i32 {
        let n = n as usize;
        let delay = delay as usize;
        let forget = forget as usize;
        let mut dp = vec![0i64; n+2];
        dp[1] = 1;
        let m = 1_000_000_007;
        for day in 1..=n {
            if dp[day] == 0 { continue; }
            for d in (day+delay)..((day+forget).min(n+1)) {
                if d <= n { dp[d] = (dp[d] + dp[day]) % m; }
            }
        }
        let mut ans = 0i64;
        for day in (n-forget+1)..=n {
            if day >= 1 { ans = (ans + dp[day]) % m; }
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    peopleAwareOfSecret(n: number, delay: number, forget: number): number {
        const MOD = 1e9+7;
        const dp = Array(n+2).fill(0);
        dp[1] = 1;
        for (let day = 1; day <= n; ++day) {
            if (dp[day] === 0) continue;
            for (let d = day+delay; d < Math.min(day+forget, n+1); ++d) {
                if (d <= n) dp[d] = (dp[d] + dp[day]) % MOD;
            }
        }
        let ans = 0;
        for (let day = n-forget+1; day <= n; ++day) {
            if (day >= 1) ans = (ans + dp[day]) % MOD;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n*forget), since for each day we may update up to forget days ahead.
  • 🧺 Space complexity: O(n), for the DP array.