Problem Description

This problem simulates the spread and forgetting of a secret among people over time.

Initial Setup:

• On day 1, exactly one person discovers a secret.

Key Rules:

1. Sharing Rule: After a person discovers the secret, they wait for delay days before they can start sharing it. Once they can share, they share the secret with exactly one new person every day.

2. Forgetting Rule: A person forgets the secret exactly forget days after discovering it. Once forgotten, they can no longer share the secret.

3. Timing Constraint: A person cannot share the secret on the same day they forget it.

Example Timeline for One Person:

• Day 1: Person discovers the secret
• Days 2 to delay: Person knows the secret but cannot share yet
• Days delay + 1 to forget - 1: Person actively shares the secret with one new person each day
• Day forget: Person forgets the secret and stops sharing

Goal: Given an integer n, determine how many people know the secret at the end of day n. Since the number can be very large, return the result modulo 10^9 + 7.

Key Insight: People who know the secret at day n are those who:

• Discovered it recently enough that they haven't forgotten it yet (within the last forget - 1 days)
• This includes both people who can share and those still in their delay period

The challenge is tracking how many people discover the secret each day and managing when they start sharing and when they forget.

Intuition

To solve this problem, we need to track two key pieces of information for each day:

1. How many people discover the secret on that day (cnt[i])
2. How many people currently know the secret (d[i] using a difference array technique)

The main insight is that each person who discovers the secret follows a predictable pattern:

• They learn the secret on some day i
• They start sharing from day i + delay
• They continue sharing until day i + forget - 1
• They forget on day i + forget

This means if cnt[i] people discover the secret on day i, then:

• These cnt[i] people will each share with 1 new person per day from day i + delay to day i + forget - 1
• These cnt[i] people will forget the secret on day i + forget

We can use a difference array technique to efficiently track who knows the secret. When someone discovers the secret on day i, we:

• Add them to the count of people who know: d[i] += cnt[i]
• Schedule their forgetting: d[i + forget] -= cnt[i]

For the sharing behavior, when cnt[i] people discover the secret on day i, they will share with others during their "active sharing window" which spans from day i + delay to day i + forget - 1. During each day in this window, cnt[i] new people will discover the secret.

The final answer is the cumulative sum of the difference array up to day n, which gives us the total number of people who know the secret on day n. The difference array naturally handles both the addition of new people learning the secret and the subtraction of people forgetting it.

This approach efficiently simulates the entire process in O(n * (forget - delay)) time, avoiding the need to track each person individually.

Learn more about Queue and Dynamic Programming patterns.

Solution Approach

The solution uses two arrays to track the secret spreading dynamics:

Data Structures:

• cnt[i]: Number of people who discover the secret on day i
• d[i]: Difference array to track people who know the secret

Implementation Steps:

1. Initialize Arrays:

   m = (n << 1) + 10  # Buffer size (2*n + 10) to avoid index out of bounds
   d = [0] * m        # Difference array
   cnt = [0] * m      # Count of new discoveries per day
   cnt[1] = 1         # One person discovers on day 1

2. Main Simulation Loop (days 1 to n):

   For each day i where people discover the secret (cnt[i] > 0):

   a. Handle Knowledge and Forgetting:

   d[i] += cnt[i]           # People discover the secret on day i
   d[i + forget] -= cnt[i]  # They forget on day i + forget

   b. Handle Sharing:

   nxt = i + delay  # Start sharing from day i + delay
   while nxt < i + forget:  # Share until day i + forget - 1
       cnt[nxt] += cnt[i]   # Each person shares with 1 new person
       nxt += 1

   The loop ensures that cnt[i] people who discovered the secret on day i will each share with one new person every day during their active sharing period [i + delay, i + forget - 1].

3. Calculate Final Answer:

   return sum(d[: n + 1]) % mod

   The cumulative sum of the difference array up to day n gives the total number of people who know the secret. We apply modulo 10^9 + 7 to handle large numbers.

Example Walkthrough:

Let's say delay = 2, forget = 4, n = 6:

• Day 1: Person 1 discovers (cnt[1] = 1)
  • Sets d[1] += 1 (knows) and d[5] -= 1 (forgets on day 5)
  • Will share on days 3 and 4
• Day 3: Person 1 shares with Person 2 (cnt[3] = 1)
• Day 4: Person 1 shares with Person 3 (cnt[4] = 1)
• Days 5-6: Person 2 and 3 continue sharing pattern

The difference array technique elegantly handles the addition and removal of people knowing the secret without explicitly tracking each person's state.

Example Walkthrough

Let's trace through a concrete example with n = 6, delay = 2, forget = 4.

Initial Setup:

• cnt[1] = 1 (one person discovers the secret on day 1)
• All other arrays start at 0

Day 1 Processing (i = 1, cnt[1] = 1):

• Update difference array:
  • d[1] += 1 (person learns secret on day 1)
  • d[5] -= 1 (person forgets on day 5)
• Schedule sharing for days 3-4 (from 1+2 to 1+4-1):
  • cnt[3] += 1 (will share with 1 person on day 3)
  • cnt[4] += 1 (will share with 1 person on day 4)

Day 2 Processing (i = 2, cnt[2] = 0):

• Nothing happens (no one discovers the secret on day 2)

Day 3 Processing (i = 3, cnt[3] = 1):

• One new person discovers the secret (shared by person from day 1)
• Update difference array:
  • d[3] += 1 (new person learns secret)
  • d[7] -= 1 (will forget on day 7, outside our range)
• Schedule sharing for days 5-6 (from 3+2 to 3+4-1):
  • cnt[5] += 1
  • cnt[6] += 1

Day 4 Processing (i = 4, cnt[4] = 1):

• Another person discovers the secret (shared by person from day 1)
• Update difference array:
  • d[4] += 1
  • d[8] -= 1 (outside our range)
• Schedule sharing for days 6-7:
  • cnt[6] += 1 (now cnt[6] = 2)
  • cnt[7] += 1

Day 5 Processing (i = 5, cnt[5] = 1):

• Person from day 3 shares
• Update difference array:
  • d[5] += 1
  • d[9] -= 1
• Schedule sharing for days 7-8 (outside our range for this problem)

Day 6 Processing (i = 6, cnt[6] = 2):

• Two people discover the secret (shared by persons from days 3 and 4)
• Update difference array:
  • d[6] += 2
  • d[10] -= 2

Final Calculation: Calculate cumulative sum of d from days 1 to 6:

• Day 1: d[1] = 1, running sum = 1
• Day 2: d[2] = 0, running sum = 1
• Day 3: d[3] = 1, running sum = 2
• Day 4: d[4] = 1, running sum = 3
• Day 5: d[5] = 1 - 1 = 0, running sum = 3
• Day 6: d[6] = 2, running sum = 5

Answer: 5 people know the secret at the end of day 6

This matches our expectation: persons from days 3, 4, 5, and 6 (4 people total) still remember, plus 2 new discoveries on day 6 minus 1 person who forgot on day 5 = 5 people.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * forget)

The algorithm uses nested loops where:

• The outer loop runs from 1 to n, iterating n times
• For each person who knows the secret at day i (when cnt[i] > 0), the inner while loop runs from i + delay to i + forget - 1
• This inner loop executes forget - delay times, which is at most forget - 1 times
• In the worst case, every day could have people knowing the secret, leading to O(n * forget) operations

Space Complexity: O(n)

The algorithm uses:

• Two arrays d and cnt, each of size m = (n << 1) + 10, which is approximately 2n + 10
• Since m is linearly proportional to n, the space complexity is O(n)
• No additional data structures that scale with input size are used

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Sharing Period

Pitfall: Incorrectly including the day when a person forgets the secret in their sharing period. The problem explicitly states that a person cannot share on the same day they forget.

Incorrect Implementation:

# Wrong: includes day i + forget
for sharing_day in range(start_sharing_day, stop_sharing_day + 1):
    new_people_each_day[sharing_day] += new_people_each_day[day]

Correct Implementation:

# Correct: stops at day i + forget - 1
for sharing_day in range(start_sharing_day, stop_sharing_day):
    new_people_each_day[sharing_day] += new_people_each_day[day]

2. Insufficient Buffer Size Leading to Index Out of Bounds

Pitfall: Using exactly n or n + forget as array size, which causes index errors when accessing day + forget positions.

Incorrect Implementation:

# Wrong: may cause index error
people_knowing_secret = [0] * (n + 1)
new_people_each_day = [0] * (n + 1)

Correct Implementation:

# Correct: provides sufficient buffer
buffer_size = (n << 1) + 10  # or simply 2 * n + forget
people_knowing_secret = [0] * buffer_size
new_people_each_day = [0] * buffer_size

3. Forgetting to Apply Modulo Operation

Pitfall: Computing the final sum without applying modulo, which can cause integer overflow for large test cases.

Incorrect Implementation:

# Wrong: missing modulo
return sum(people_knowing_secret[:n + 1])

Correct Implementation:

# Correct: applies modulo
MOD = 10**9 + 7
return sum(people_knowing_secret[:n + 1]) % MOD

4. Misunderstanding the Difference Array Concept

Pitfall: Thinking the difference array directly represents the number of people who know the secret on each day. The actual count requires computing the cumulative sum.

Incorrect Implementation:

# Wrong: returns value at day n instead of cumulative sum
return people_knowing_secret[n] % MOD

Correct Implementation:

# Correct: returns cumulative sum up to day n
return sum(people_knowing_secret[:n + 1]) % MOD

5. Incorrect Handling of Delay Period

Pitfall: Starting to share immediately or miscalculating when sharing begins.

Key Points to Remember:

• A person discovers the secret on day i
• They start sharing on day i + delay (not i + delay - 1 or i + delay + 1)
• They stop sharing on day i + forget - 1 (the day before they forget)