2327. Number of People Aware of a Secret
Problem Description
This LeetCode problem presents a scenario in which a secret spreads among people according to specific rules. On the first day, one person discovers a secret. Two parameters, delay
and forget
, govern how the secret spreads:
delay
: The number of days after a person discovers the secret before they begin sharing it every day.forget
: The number of days after discovering the secret when a person forgets it and stops sharing.
The goal is to calculate how many people know the secret at the end of n
days. To handle large numbers, the result should be returned modulo 10^9 + 7
, a common practice to prevent integer overflow in programming contests.
Intuition
The solution strategy involves simulating the sharing and forgetting process over n
days, while efficiently tracking the count of people who know the secret and can still share it. The key steps are:
-
Tracking the Spread and Forgetting: The number of people who can share the secret changes over time and needs to be accurately tracked each day, from the day they start sharing to the day they forget the secret.
-
Cumulative Counting: Instead of updating individual counts every day, the solution uses a cumulative count approach to record changes in a manner that allows for all future updates at once.
-
Daily Update: The code simulates each day, updating the count of people who will share and forget the secret in the future.
-
Modular Arithmetic: Since the final answer can be very large, it's necessary to use modular arithmetic to keep the numbers within bounds and compute the result modulo
10^9 + 7
.
This is how the code arrives at the solution:
- An array
d
(with a size comfortably larger than twicen
) is used to keep track of daily changes ā how many people discover and forget the secret each day. - An array
cnt
records the number of new people who know the secret on a particular day. - A loop runs for each day from
1
ton
and updatesd
andcnt
accordingly. Whenever a person learns the secret, the future changes (both the sharing and forgetting) are recorded ind
. - Since a person can share the secret starting from
delay
days after learning it until they forget it, a nested loop calculates all the days when the person is supposed to share the secret and updatescnt
. - At the end of the simulation, the sum of
d
up to dayn
(inclusive) represents the total number of people who learned (and have not forgotten) the secret. This sum is taken modulo10^9 + 7
to get the final answer.
Learn more about Queue and Dynamic Programming patterns.
Solution Approach
The following is an implementation walkthrough based on the provided Python solution.
-
Initialization:
- An array
d
is initialized with sizem
, wherem
is an arbitrary number greater than twicen
to ensure enough space for the entire timeline of events (people discovering the secret and then forgetting it). - An array
cnt
is also initialized with the same sizem
, to track the number of new people who know the secret each day. The first person knows the secret on day1
, socnt[1]
is set to1
.
- An array
-
Simulation Loop:
- A loop runs from day
1
to dayn
, simulating the spread and forgetfulness of the secret over time. Ifcnt[i]
is not zero (meaning people discovered the secret on that day), the process begins.
- A loop runs from day
-
Updating Future Events:
- Two future events are updated in the
d
array for each person that knows the secret on dayi
: a. The day they will start sharing the secret (i + delay
). b. The day they will forget the secret (i + forget
), on which the count will decrease bycnt[i]
.
- Two future events are updated in the
-
Sharing the Secret:
- A nested loop calculates all the days between the day they can start sharing (
i + delay
) and the day before they forget the secret (i + forget
), incrementally updatingcnt[nxt]
withcnt[i]
. This loop essentially schedules the new people who will learn the secret in the future.
- A nested loop calculates all the days between the day they can start sharing (
-
Modular Arithmetic:
- A
mod
variable is defined as10**9 + 7
. The solution ensures that all operations involving the count use this modulus to prevent integer overflow and adhere to the problem's constraints.
- A
-
Final Count:
- At the end of the simulation, the sum of
d
array up ton + 1
gives the total number of people that know the secret by dayn
. This sum is then taken modulo10^9 + 7
to obtain the final result.
- At the end of the simulation, the sum of
Notice that the solution utilizes the "prefix sum" array pattern through array d
. By marking the start and end of an event with incremental and decremental values in d
, it becomes possible to compute cumulative effects with only a single summation at the end. This avoids the need for multiple loops or updates within the main simulation, thereby optimizing performance.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have the parameters n
= 5 (days), delay
= 1, and forget
= 3. We want to find how many people will know the secret at the end of the 5 days.
-
Initialization:
- We initialize the array
d
with sizem = 2*n + 1
to ensure there's more than enough space. - The array
cnt
is also initialized similarly, andcnt[1]
is set to1
because the first person knows the secret on day1
.
- We initialize the array
-
Simulation Start:
- We start iterating over the days, from day
1
to dayn
(5).
- We start iterating over the days, from day
Day 1:
- cnt[1]
= 1, which means one person knows the secret on the first day.
- They start sharing the secret after delay
days, so d[1 + delay] = d[2]
is incremented by 1 (the number of people who learned the secret on day 1).
- They will forget the secret after forget
days, so d[1 + forget] = d[4]
is decremented by 1.
Day 2:
- The person who learned the secret on day 1 starts sharing it today.
- cnt[2]
becomes 1
because d[2]
was previously updated.
- They will share it for the next couple of days, so we will have again d[2 + delay] = d[3]
incremented by 1
and d[2 + forget] = d[5]
decremented by 1.
Day 3:
- We have one more person sharing the secret (from the sharing on day 2).
- cnt[3]
is incremented by cnt[2]
which is 1, so cnt[3]
is now 1
.
- Similar to before, d[3 + delay] = d[4]
is incremented by cnt[3]
which is 1, and d[3 + forget] = d[6]
decremented by 1.
Day 4:
- Two people are sharing the secret (the original person and one more from the sharing on day 2), but the first person will forget the secret today.
- cnt[4]
is equal to d[4]
, which is the sum of increments and decrements up to this day: cnt[4] = d[2] + d[4]
= 1 + 1 - 1 = 1.
- Again, these people will cause two increases in d[4 + delay] = d[5]
by their count (which is 1), and d[4 + forget] = d[7]
is decremented by 1. But remember, the first person will not contribute to future sharings since they have forgotten.
Day 5:
- Now we have people who learned the secret from day 3 sharing it.
- cnt[5]
is derived from d[5]
, which is incremented by the count from day 4 (only one person is effectively sharing since the first person forgot).
- No more future updates to d
are necessary since we have reached our last day n
.
- Final Counting:
- Cumulate
cnt
up to dayn + 1
to determine the number of people who currently know the secret. For this example, the total is1 + 1 + 1 + 1
, since we didn't reach day 7 when the additional decrement would happen. - The sum is 4, which is the total count of people who know the secret after 5 days.
- Cumulate
The result is that 4 people know the secret at the end of day 5, respecting the delay
and forget
constraints. This example helps to illustrate the array updating and prefix sum technique used to solve the problem efficiently.
Solution Implementation
1class Solution:
2 def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
3 # Initialize a large enough array to handle the propagation of information.
4 max_days = (n << 1) + 10 # Bitwise left shift 'n' by 1 to double it, and add 10 for buffer
5 secret_knowledge_counts = [0] * max_days # Array to track the number of people who know the secret
6 current_day_counts = [0] * max_days # Array to track the number of people who will share the secret per day
7
8 # On day 1, one person knows the secret.
9 current_day_counts[1] = 1
10
11 # Loop over each day up to 'n' to simulate the sharing and forgetting process.
12 for day in range(1, n + 1):
13 if current_day_counts[day]: # If there are people to share the secret on this day
14 # Increment the count of people who will know the secret because of sharing.
15 secret_knowledge_counts[day] += current_day_counts[day]
16 # Decrease the count of people who will remember the secret after they forget.
17 secret_knowledge_counts[day + forget] -= current_day_counts[day]
18
19 # Day when the current people are allowed to start sharing the secret.
20 next_share_day = day + delay
21
22 # Loop until the forget day to increment the count of people who will share the secret.
23 while next_share_day < day + forget:
24 current_day_counts[next_share_day] += current_day_counts[day]
25 next_share_day += 1
26
27 # Modulo value for the final calculation as per the problem statement, to avoid large integers.
28 modulo = 10 ** 9 + 7
29
30 # Sum all the people who know the secret up to day 'n' and return the result modulo `modulo`.
31 return sum(secret_knowledge_counts[: n + 1]) % modulo
32
1class Solution {
2 // Constant for modulo operation to ensure the numbers do not get too large.
3 private static final int MOD = (int) 1e9 + 7;
4
5 public int peopleAwareOfSecret(int n, int delay, int forget) {
6 // A buffer is added to manage the maximum days needed.
7 int bufferLength = (n << 1) + 10;
8
9 // Daily increase tracker.
10 long[] dailyIncrease = new long[bufferLength];
11
12 // People count tracker for each day.
13 long[] peopleCount = new long[bufferLength];
14
15 // Initially, on day 1, one person knows the secret.
16 peopleCount[1] = 1;
17
18 // Loop through each day.
19 for (int i = 1; i <= n; ++i) {
20 // If peopleCount[i] is positive, proceed to share the secret.
21 if (peopleCount[i] > 0) {
22 // Add to the dailyIncrease.
23 dailyIncrease[i] = (dailyIncrease[i] + peopleCount[i]) % MOD;
24
25 // Subtract from the dailyIncrease after the forgetting period.
26 dailyIncrease[i + forget] = (dailyIncrease[i + forget] - peopleCount[i] + MOD) % MOD;
27
28 // Compute the next day when sharing starts, and continue until the forgetting day.
29 int nextShareDay = i + delay;
30 while (nextShareDay < i + forget) {
31 peopleCount[nextShareDay] = (peopleCount[nextShareDay] + peopleCount[i]) % MOD;
32 ++nextShareDay;
33 }
34 }
35 }
36
37 // Calculate the final answer by summing dailyIncrease for each day.
38 long answer = 0;
39 for (int i = 1; i <= n; ++i) {
40 answer = (answer + dailyIncrease[i]) % MOD;
41 }
42
43 // Return the final number of people aware of the secret as an integer.
44 return (int) answer;
45 }
46}
47
1using ll = long long;
2const int MOD = 1e9 + 7;
3
4class Solution {
5public:
6 // This function calculates the number of people aware of a secret after 'n' days,
7 // with a certain delay before they can share the secret and a forget time.
8 int peopleAwareOfSecret(int n, int delay, int forget) {
9 // Calculating array size to be sufficiently large
10 int arraySize = (n << 1) + 10;
11
12 vector<ll> incrementArray(arraySize, 0); // Array to handle increments of people knowing the secret
13 vector<ll> peopleCountArray(arraySize, 0); // People knowing the secret by day i
14
15 // Initially, one person knows the secret
16 peopleCountArray[1] = 1;
17
18 // Process each day
19 for (int day = 1; day <= n; ++day) {
20 // Skip days when no new people are aware of the secret
21 if (!peopleCountArray[day]) continue;
22
23 // Schedule an increase in the count for the current day
24 incrementArray[day] = (incrementArray[day] + peopleCountArray[day]) % MOD;
25 // Schedule a decrease (forgetting) in the count after the forgetting period
26 incrementArray[day + forget] = (incrementArray[day + forget] - peopleCountArray[day] + MOD) % MOD;
27
28 // Spread the secret to new people after the delay, every day until they forget
29 int shareDay = day + delay;
30 while (shareDay < day + forget) {
31 peopleCountArray[shareDay] = (peopleCountArray[shareDay] + peopleCountArray[day]) % MOD;
32 ++shareDay;
33 }
34 }
35
36 // Calculate the final answer, the total number of people aware of the secret after 'n' days
37 int totalAwarePeople = 0;
38 for (int day = 1; day <= n; ++day) {
39 totalAwarePeople = (totalAwarePeople + incrementArray[day]) % MOD;
40 }
41 return totalAwarePeople;
42 }
43};
44
1function peopleAwareOfSecret(n: number, delay: number, forget: number): number {
2 // Initialize an array to track the number of people who know the secret each day.
3 // Using BigInt for large numbers as the result can be quite large.
4 let peopleAware = new Array(n + 1).fill(0n);
5
6 // The first person knows the secret on the first day.
7 peopleAware[1] = 1n;
8
9 // Iterate over each day to find out how many people are aware of the secret
10 for (let day = 2; day <= n; day++) {
11 // Variable to store the number of people that start sharing the secret.
12 let peopleSharing = 0n;
13
14 // Calculate the number of people that will share the secret today looking back at
15 // the window of days where people are able to share the secret,
16 // i.e., from `day - forget + 1` to `day - delay`
17 for (let shareDay = day - forget + 1; shareDay <= day - delay; shareDay++) {
18 if (shareDay > 0) {
19 peopleSharing += peopleAware[shareDay];
20 }
21 }
22
23 // Update the current number of aware people.
24 peopleAware[day] = peopleSharing;
25 }
26
27 // Variable to aggregate the total number of people who remember the secret
28 // on the last day subtracting those who have forgotten
29 let finalTotal = 0n;
30
31 // Start reviewing from the last day subtracting the forget period
32 for (let countDay = n - forget + 1; countDay <= n; countDay++) {
33 if (countDay > 0) {
34 finalTotal += peopleAware[countDay];
35 }
36 }
37
38 // Return the number of people who are aware of the secret on the last day modulo 10^9 + 7, converting BigInt to number
39 return Number(finalTotal % BigInt(10 ** 9 + 7));
40}
41
Time and Space Complexity
The given Python function peopleAwareOfSecret
computes the number of people aware of a secret on the n
-th day, under certain conditions of delay before sharing and forgetting the secret. The function implements a form of dynamic programming using arrays to simulate the process over n
days.
Time Complexity:
- The function has a primary loop that iterates over the range
1
ton + 1
, which gives us anO(n)
component. - Inside this loop, there's a secondary while loop, for sharing the secret from the
i + delay
-th to thei + forget - 1
-th day. In the worst case scenario, this while loop executes(forget - delay)
times. Therefore, its contribution isO(forget - delay)
. - Since both loops are nested and the while loop runs for every value of
i
, we might initially consider the time complexity to beO(n * (forget - delay))
.
However, the variable nxt
is being incremented by 1 on each iteration without being reset for every i
, and when reaching i + forget
, the loop exits. Therefore, every element in the range 1
to n
can only contribute to at most (forget - delay)
increments over the entire function execution. Thus, the while-loop does not lead to a full cartesian product across n
and (forget - delay)
.
The actual time complexity is thus O(n + forget)
.
Space Complexity:
- Two arrays
d
andcnt
of maximum sizem
are used, wherem = (n << 1) + 10
- sort of a safe upper bound to ensure the array can handle the indices that the algorithm will access. These arrays are the main contributors to space complexity. - Thus, the space complexity of the function is
O(m)
, which simplifies toO(n)
sincem
is just a linear scaling ofn
.
To summarize:
- Time Complexity:
O(n + forget)
- Space Complexity:
O(n)
Learn more about how to find time and space complexity quickly using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!