#2327

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of People Aware of a Secret

Calculate how many people know a secret over n days using state transition dynamic programming and careful simulation of sharing and forgetting.

dynamic programming queue simulation

Problem Statement

On day 1, a single person discovers a secret. Each person can share the secret with a new person starting from 'delay' days after learning it, and will forget the secret 'forget' days after learning it. A person cannot share the secret on the day they forget it or any day after.

Given integers n, delay, and forget, determine how many people know the secret at the end of day n. Return the answer modulo 10^9 + 7. Constraints: 2 <= n <= 1000, 1 <= delay < forget <= n.

Examples

Example 1

Input: n = 6, delay = 2, forget = 4

Output: 5

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

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

Solution Approach

Model Daily States with DP

Define dp[i][j] as the number of people who have known the secret for exactly j + 1 days on day i. This structure lets you track who can share and who forgets efficiently each day, following the state transition dynamic programming pattern.

Iterate Over Days

For each day from 1 to n, update dp[i][j] based on previous states: add new people shared the secret by those eligible, and remove people who forget today. Use modulo 10^9 + 7 to avoid overflow.

Compute Total Aware People

After processing all days, sum all dp[n][j] values for j from 0 to forget-1 to get the total number of people aware of the secret at day n. This handles both sharing and forgetting states accurately.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * forget) because we iterate over each day and track up to 'forget' days of states. Space complexity is O(n * forget) for the DP table but can be optimized to O(forget) using rolling arrays.

What Interviewers Usually Probe

Emphasize your DP state and why each state represents people aware for exact days.
Explain how the delay and forget constraints affect the sharing process.
Discuss rolling array optimization to reduce space complexity.

Common Pitfalls or Variants

Common pitfalls

Forgetting to exclude people from sharing on the day they forget.
Incorrectly summing states, counting those who already forgot.
Confusing delay and forget days, leading to off-by-one errors in DP indices.

Follow-up variants

Calculate the total number of people aware if multiple people discover the secret on different days.
Find the earliest day when the number of people aware reaches a target value.
Modify the problem to allow sharing with multiple people per day instead of just one.

FAQ

What is the main approach to solve Number of People Aware of a Secret?

Use state transition dynamic programming to track the number of people aware each day, considering delay before sharing and forgetting after a set period.

How do delay and forget affect the simulation?

Delay determines when a person starts sharing, while forget determines when they stop, directly impacting daily state updates in DP.

Can space be optimized in this DP solution?

Yes, a rolling array can reduce space from O(n * forget) to O(forget) by only keeping the previous day's states.

Why use modulo 10^9 + 7?

The number of people aware can grow exponentially, so modulo prevents integer overflow and keeps calculations within bounds.

What is a common off-by-one mistake in this problem?

Misaligning delay and forget indices in the DP table, leading to counting people too early or after they forget.

terminal

Solution

Solution 1: Difference Array

We use a difference array $d[i]$ to record the change in the number of people who know the secret on day $i$, and an array $cnt[i]$ to record the number of people who newly learn the secret on day $i$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        m = (n << 1) + 10
        d = [0] * m
        cnt = [0] * m
        cnt[1] = 1
        for i in range(1, n + 1):
            if cnt[i]:
                d[i] += cnt[i]
                d[i + forget] -= cnt[i]
                nxt = i + delay
                while nxt < i + forget:
                    cnt[nxt] += cnt[i]
                    nxt += 1
        mod = 10**9 + 7
        return sum(d[: n + 1]) % mod

Continue Practicing

#2380 time needed to rearrange a binary string #2407 longest increasing subsequence ii #2073 time needed to buy tickets