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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of People Aware of a Secret

Difficulty: Medium

Problem Description

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 10^9 + 7.

Key Insights

  • The first person discovers the secret on day 1.
  • Each person starts sharing the secret after delay days and forgets it after forget days.
  • The total number of people who know the secret can be computed dynamically based on the number of people who shared the secret each day.
  • The problem can be solved using a dynamic programming approach where we track the number of new people who learn the secret each day.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a dynamic programming approach where we maintain an array to keep track of how many new people learn the secret each day. We initialize the first day with 1 person who knows the secret. For each subsequent day, we calculate how many people can share the secret based on the delay and forget parameters. Specifically, for each day, we sum the contributions from all the people who are still aware of the secret and share it with new individuals. We ensure we apply the modulo operation to avoid overflow.

Code Solutions

def peopleAwareOfSecret(n, delay, forget):
    MOD = 10**9 + 7
    dp = [0] * (n + 1)
    dp[1] = 1  # On day 1, 1 person knows the secret

    for day in range(2, n + 1):
        # Calculate how many people share the secret on this day
        for j in range(delay, forget):
            if day - j >= 1:
                dp[day] = (dp[day] + dp[day - j]) % MOD
        # A person who learned the secret today
        if day >= delay:
            dp[day] = (dp[day] + dp[day - delay]) % MOD
        # A person who forgets today
        if day >= forget:
            dp[day] = (dp[day] - dp[day - forget] + MOD) % MOD

    return sum(dp[day] for day in range(n + 1) if day >= 1) % MOD
← Back to All Questions