Skip to content

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<int> dp(n);  // Map day i to i + 1
    dp[0] = 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[0] = 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 = [0] * n  # Map day i to i + 1
    dp[0] = 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