# 2327. Number of People Aware of a Secret     • Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: int peopleAwareOfSecret(int n, int delay, int forget) { constexpr int kMod = 1'000'000'007; long share = 0; // dp[i] := # of people know the secret at day i vector dp(n); // Map day i to i + 1 dp = 1; for (int i = 1; i < n; ++i) { if (i - delay >= 0) share += dp[i - delay]; if (i - forget >= 0) share -= dp[i - forget]; share += kMod; share %= kMod; dp[i] = share; } // People before day n - forget - 1 already forget the secret return accumulate(end(dp) - forget, end(dp), 0, [&](int subtotal, int d) { return (subtotal + d) % kMod; }); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public int peopleAwareOfSecret(int n, int delay, int forget) { final int kMod = 1_000_000_007; long share = 0; // dp[i] := # of people know the secret at day i int[] dp = new int[n]; // Map day i to i + 1 dp = 1; for (int i = 1; i < n; ++i) { if (i - delay >= 0) share += dp[i - delay]; if (i - forget >= 0) share -= dp[i - forget]; share += kMod; share %= kMod; dp[i] = (int) share; } // People before day n - forget - 1 already forget the secret int ans = 0; for (int i = n - forget; i < n; ++i) ans = (ans + dp[i]) % kMod; return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int: kMod = 1_000_000_007 share = 0 # dp[i] := # of people know the secret at day i dp =  * n # Map day i to i + 1 dp = 1 for i in range(1, n): if i - delay >= 0: share += dp[i - delay] if i - forget >= 0: share -= dp[i - forget] share += kMod share %= kMod dp[i] = share # People before day n - forget - 1 already forget the secret return sum(dp[-forget:]) % kMod