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:

  1. 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.

  2. 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.

  3. Daily Update: The code simulates each day, updating the count of people who will share and forget the secret in the future.

  4. 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 twice n) 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 to n and updates d and cnt accordingly. Whenever a person learns the secret, the future changes (both the sharing and forgetting) are recorded in d.
  • 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 updates cnt.
  • At the end of the simulation, the sum of d up to day n (inclusive) represents the total number of people who learned (and have not forgotten) the secret. This sum is taken modulo 10^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.

  1. Initialization:

    • An array d is initialized with size m, where m is an arbitrary number greater than twice n 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 size m, to track the number of new people who know the secret each day. The first person knows the secret on day 1, so cnt[1] is set to 1.
  2. Simulation Loop:

    • A loop runs from day 1 to day n, simulating the spread and forgetfulness of the secret over time. If cnt[i] is not zero (meaning people discovered the secret on that day), the process begins.
  3. Updating Future Events:

    • Two future events are updated in the d array for each person that knows the secret on day i: 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 by cnt[i].
  4. 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 updating cnt[nxt] with cnt[i]. This loop essentially schedules the new people who will learn the secret in the future.
  5. Modular Arithmetic:

    • A mod variable is defined as 10**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.
  6. Final Count:

    • At the end of the simulation, the sum of d array up to n + 1 gives the total number of people that know the secret by day n. This sum is then taken modulo 10^9 + 7 to obtain the final result.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

Example 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.

  1. Initialization:

    • We initialize the array d with size m = 2*n + 1 to ensure there's more than enough space.
    • The array cnt is also initialized similarly, and cnt[1] is set to 1 because the first person knows the secret on day 1.
  2. Simulation Start:

    • We start iterating over the days, from day 1 to day n (5).

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.

  1. Final Counting:
    • Cumulate cnt up to day n + 1 to determine the number of people who currently know the secret. For this example, the total is 1 + 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.

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 to n + 1, which gives us an O(n) component.
  • Inside this loop, there's a secondary while loop, for sharing the secret from the i + delay-th to the i + forget - 1-th day. In the worst case scenario, this while loop executes (forget - delay) times. Therefore, its contribution is O(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 be O(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 and cnt of maximum size m are used, where m = (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 to O(n) since m is just a linear scaling of n.

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.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄