Number of People Aware of a Secret

main.md

Question

Approach

I use dynamic programming where new[d] is how many people learn the secret on day d. The first person gives new[1] = 1. A person who learned on day t starts sharing from day t+delay and stops after day t+forget-1. So the number of people actively sharing on day d is a sliding-window sum over new[d-delay .. d-forget+1]. I maintain this window with two updates per day: add new[d-delay] when it enters, subtract new[d-forget] when it leaves. Then new[d] = sharers because every sharer tells exactly one new person that day. At the end, the number of people who still know the secret is those who learned in the last forget-1 days: sum of new[d] for d ∈ [n-forget+1, n] (mod $10^9+7$).

Implementation

MOD = 10**9 + 7

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        new = [0] * (n + 1)
        new[1] = 1

        sharers = 0
        for day in range(2, n + 1):
            start_idx = day - delay
            if start_idx >= 1:
                sharers = (sharers + new[start_idx]) % MOD
            end_idx = day - forget
            if end_idx >= 1:
                sharers = (sharers - new[end_idx]) % MOD
            new[day] = sharers

        ans = 0
        for day in range(max(1, n - forget + 1), n + 1):
            ans = (ans + new[day]) % MOD
        return ans

Complexities

• Time: O(n)
• Space: O(n)