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)
Example 2:
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 <= 10001 <= delay < forget <= nThis approach involves using a dynamic programming array to keep track of people who can start sharing the secret on a particular day. We'll calculate how many new people learn the secret each day and how many forget it. By maintaining a record of new sharers, we can update daily totals efficiently.
In this C solution, two arrays, dp and share, are used. dp[i] records the total count of people knowing the secret on day i. share[i] represents the count of people who are in their sharing period starting on day i. The iteration considers:
delay period.forget period.dp[n] as the final result modulo 10^9 + 7.C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n)
This approach optimizes for space by not explicitly storing each day's state, retaining only necessary counters and calculating values iteratively. Instead of a long-term history, this method tracks incremental gains daily.
By using only an array with the size of 'forget', this Python function calculates the state of the secret sharers. The array acts as a rotating block capturing only necessary states of dp. The rolling calculation of total keeps the logic sound without needing a full recapture each day.
Time Complexity: O(n)
Space Complexity: O(forget)
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n) |
| Optimized Constant Space Approach | Time Complexity: O(n) |
Find All People With Secret - Leetcode 2092 - Python • NeetCodeIO • 15,259 views views
Watch 9 more video solutions →Practice Number of People Aware of a Secret with our built-in code editor and test cases.
Practice on FleetCode