Leetcode 2327: Number of People Aware of a Secret
On day 1, one person discovers a secret. Each person will share the secret after a delay and forget it after a certain number of days. Return the number of people who know the secret at the end of day n, modulo 10^9 + 7.
Problem
Approach
Steps
Complexity
Input: You are given integers n (number of days), delay (days after which a person starts sharing the secret), and forget (days after which a person forgets the secret).
Example: n = 6, delay = 2, forget = 4
Constraints:
• 2 <= n <= 1000
• 1 <= delay < forget <= n
Output: Return the number of people who know the secret at the end of day n, modulo 10^9 + 7.
Example: Output: 5
Constraints:
• The answer can be very large, so return it modulo 10^9 + 7.
Goal: Simulate the process of sharing and forgetting the secret over n days.
Steps:
• Initialize an array to track the number of people sharing the secret each day.
• Use dynamic programming to calculate how the secret spreads over time, considering the delay and forget intervals.
• Return the sum of the people who know the secret at the end of day n.
Goal: The values for n, delay, and forget are constrained as described in the input representation.
Steps:
• 2 <= n <= 1000
• 1 <= delay < forget <= n
Assumptions:
• There is at least one person who knows the secret on day 1.
• Each person can share the secret only once during the period they know it.
• Input: n = 6, delay = 2, forget = 4
• Explanation: This example demonstrates how the secret spreads over 6 days, with the delay and forget intervals affecting how many people eventually learn the secret.
Approach: The goal is to simulate the process of how a secret is shared and forgotten over time using dynamic programming.
Observations:
• Each person can only share the secret once, and they will forget after a certain number of days.
• We need to track how many people share the secret each day, considering the delay and forget intervals.
Steps:
• 1. Initialize an array to track the people sharing the secret.
• 2. Simulate the process day by day, updating the count of people who share the secret each day.
• 3. Return the number of people who know the secret at the end of day n, modulo 10^9 + 7.
Empty Inputs:
• n = 2, delay = 1, forget = 2
Large Inputs:
• n = 1000, delay = 500, forget = 800
Special Values:
• delay = 1, forget = 3
Constraints:
• The number of people sharing the secret and forgetting it must be correctly managed with respect to the provided constraints.
int peopleAwareOfSecret(int n, int delay, int forget) {
int res = 0, share = 0;
vector<long> dp(n + 2, 0);
dp[1] = 1;
int mod = 1e9 + 7;
for(int i = 2; i <= n; i++)
dp[i] = share = (share + dp[max(i - delay, 0)] - dp[max(i - forget, 0)] + mod) % mod;
for(int i = n + 1 - forget; i <= n; i++)
res = (res + dp[i]) % mod;
return res;
}
1 : Function Declaration
int peopleAwareOfSecret(int n, int delay, int forget) {
Declares the function `peopleAwareOfSecret` that takes three parameters: `n` (the total number of days), `delay` (the number of days before a person can share the secret), and `forget` (the number of days after which a person forgets the secret). It returns the total number of people aware of the secret modulo `1e9 + 7`.
2 : Variable Initialization
int res = 0, share = 0;
Initializes two variables: `res` to store the result (number of people aware of the secret) and `share` to track the number of people who can share the secret on any given day.
3 : Dynamic Programming Setup
vector<long> dp(n + 2, 0);
Initializes a dynamic programming (DP) vector `dp` of size `n + 2` to store the number of people who are aware of the secret on each day. The extra space is for handling boundary conditions safely.
4 : Base Case
dp[1] = 1;
Sets the base case: on day 1, one person knows the secret.
5 : Modular Arithmetic
int mod = 1e9 + 7;
Defines a constant `mod` with the value `1e9 + 7` for performing modular arithmetic to prevent overflow and ensure the result fits within standard integer limits.
6 : Dynamic Programming Loop
for(int i = 2; i <= n; i++)
Iterates through each day from 2 to `n` to calculate the number of people who are aware of the secret on that day.
7 : State Transition
dp[i] = share = (share + dp[max(i - delay, 0)] - dp[max(i - forget, 0)] + mod) % mod;
Updates the value of `dp[i]`, which represents the number of people who become aware of the secret on day `i`. It adds the number of people who can share the secret (after the `delay` period) and subtracts those who forget it (after the `forget` period). The result is taken modulo `mod`.
8 : Final Summation
for(int i = n + 1 - forget; i <= n; i++)
Iterates through the last `forget` days to sum the number of people who are still aware of the secret.
9 : Result Update
res = (res + dp[i]) % mod;
Adds the number of people aware of the secret on day `i` to `res`, taking care to apply modular arithmetic to avoid overflow.
10 : Return Statement
return res;
Returns the total number of people who are aware of the secret, modulo `1e9 + 7`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear in terms of n, as we iterate through each day once.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is also linear, as we need an array to track people each day.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus