Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2327.html
2327. Number of People Aware of a Secret
- Difficulty: Medium.
- Related Topics: Dynamic Programming, Queue, Simulation.
- Similar Questions: .
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
Solution (Java, C++, Python)
-
class Solution { public int peopleAwareOfSecret(int n, int delay, int forget) { long[][] dp = new long[n + forget][3]; // 0: people who currently know the secret (includes [1] below) // 1: people who start sharing the secret on this day // 2: people who forget on this day long mod = (long) 1e9 + 7; dp[0][0] = dp[delay][1] = dp[forget][2] = 1; for (int i = 1; i < n; i++) { // dp[i][1] was originally just the i - delay newcomers dp[i][1] = (dp[i][1] + dp[i - 1][1] - dp[i][2] + mod) % mod; // these people forget on i + forget day dp[i + forget][2] = dp[i][1]; // these people start sharing on i + delay day dp[i + delay][1] = dp[i][1]; // today's total people who know the secret dp[i][0] = (dp[i - 1][0] + dp[i][1] - dp[i][2] + mod) % mod; } return (int) dp[n - 1][0]; } } ############ class Solution { private static final int MOD = (int) 1e9 + 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; } }
-
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 ############ # 2327. Number of People Aware of a Secret # https://leetcode.com/problems/number-of-people-aware-of-a-secret/ class Solution: def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int: M = 10 ** 9 + 7 res = 1 canShare = defaultdict(int) toForget = defaultdict(int) toForget[forget + 1] = 1 propagate = 1 for day in range(delay + 1, n + 1): propagate += canShare[day] propagate -= toForget[day] res += propagate res -= toForget[day] res %= M canShare[day + delay] += propagate toForget[day + forget] += propagate return res % M
-
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; } };
-
func peopleAwareOfSecret(n int, delay int, forget int) int { m := (n << 1) + 10 d := make([]int, m) cnt := make([]int, m) mod := int(1e9) + 7 cnt[1] = 1 for i := 1; i <= n; i++ { if cnt[i] == 0 { continue } d[i] = (d[i] + cnt[i]) % mod d[i+forget] = (d[i+forget] - cnt[i] + mod) % mod nxt := i + delay for nxt < i+forget { cnt[nxt] = (cnt[nxt] + cnt[i]) % mod nxt++ } } ans := 0 for i := 1; i <= n; i++ { ans = (ans + d[i]) % mod } return ans }
-
function peopleAwareOfSecret(n: number, delay: number, forget: number): number { let dp = new Array(n + 1).fill(0n); dp[1] = 1n; for (let i = 2; i <= n; i++) { let pre = 0n; for (let j = i - forget + 1; j <= i - delay; j++) { if (j > 0) { pre += dp[j]; } } dp[i] = pre; } let pre = 0n; let i = n + 1; for (let j = i - forget; j < i; j++) { if (j > 0) { pre += dp[j]; } } return Number(pre % BigInt(10 ** 9 + 7)); }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).