2327. Number of People Aware of a Secret LeetCode Solution
In this guide, you will get 2327. Number of People Aware of a Secret LeetCode Solution with the best time and space complexity. The solution to Number of People Aware of a Secret problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of People Aware of a Secret
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)
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2327. Number of People Aware of a Secret LeetCode Solution in C++
class Solution {
public:
int peopleAwareOfSecret(int n, int delay, int forget) {
constexpr int kMod = 1'000'000'007;
long share = 0;
// dp[i] := the number of people know the secret at day i
vector<int> dp(n); // Maps 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(dp.end() - forget, dp.end(), 0, [&](int subtotal, int d) {
return (subtotal + d) % kMod;
});
}
}; /* code provided by PROGIEZ */
2327. Number of People Aware of a Secret LeetCode Solution in Java
class Solution {
public int peopleAwareOfSecret(int n, int delay, int forget) {
final int kMod = 1_000_000_007;
long share = 0;
// dp[i] := the number of people know the secret at day i
int[] dp = new int[n]; // Maps 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;
}
} // code provided by PROGIEZ
2327. Number of People Aware of a Secret LeetCode Solution in Python
class Solution:
def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
kMod = 1_000_000_007
share = 0
# dp[i] := the number of people know the secret at day i
dp = [0] * n # Maps 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 # code by PROGIEZ
