We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of People Aware of a Secret

Number: 2408

Difficulty: Medium

Paid? No

Companies: Arcesium

Problem Description

On day 1, one person discovers a secret. Each person who knows the secret will share it with a new person every day starting from delay days after learning it. However, each person forgets the secret forget days after discovering it and cannot share it on the day they forget or afterwards. Given a day n, determine the number of people who still remember (i.e. have not forgotten) the secret at the end of day n. The answer should be returned modulo 10^9+7.

Key Insights

  • Use dynamic programming to simulate the number of new people who learn the secret each day.
  • Track when people become eligible to share (after delay days) and when they forget the secret (after forget days).
  • Utilize prefix sums (cumulative sums) to efficiently compute the range sum of contributions for each day.
  • The final answer is the sum of new persons who still remember the secret (i.e., those whose discovery day is >= n - forget + 1).

Space and Time Complexity

Time Complexity: O(n) – We iterate through days 1 to n once. Space Complexity: O(n) – We store dp and prefix arrays for days 1 through n.

Solution

We simulate day by day using two arrays:

  • dp[i]: the number of people who learn the secret on day i.
  • prefix[i]: the cumulative sum of dp from day 1 to day i.

For each day i (starting from day 2), the number of new people who learn the secret, dp[i], is calculated as the sum of contributions from those who learned the secret between day i-delay and i-1 (inclusive), minus those who have already forgotten (i.e., those from day i-forget and earlier). The prefix array allows us to quickly compute these segment sums. Finally, the answer is the sum of dp values for days when individuals still remember the secret at day n (i.e., those from day n-forget+1 to day n).

Code Solutions

MOD = 10**9 + 7

def peopleAwareOfSecret(n, delay, forget):
    # Initialize dp and prefix arrays.
    dp = [0] * (n + 1)
    prefix = [0] * (n + 1)
    
    # On day 1, one person discovers the secret.
    dp[1] = 1
    prefix[1] = 1
    
    # For each day from 2 to n, determine how many new people learn the secret.
    for day in range(2, n + 1):
        # Calculate the start contribution: people eligible to share from day "day-delay".
        if day - delay >= 1:
            share_start = prefix[day - delay]
        else:
            share_start = 0
        
        # Subtract those who have forgotten the secret.
        if day - forget >= 1:
            forget_end = prefix[day - forget]
        else:
            forget_end = 0
        
        dp[day] = (share_start - forget_end) % MOD
        prefix[day] = (prefix[day - 1] + dp[day]) % MOD

    # Sum up individuals who have not forgotten the secret by day n.
    total = 0
    # People that discovered the secret on day d will still remember if d > n - forget.
    for day in range(n - forget + 1, n + 1):
        if day >= 1:
            total = (total + dp[day]) % MOD
    return total

# Example usage:
print(peopleAwareOfSecret(6, 2, 4))
← Back to All Questions