Number of People Aware of a Secret - Practice Coding Problems

Number of People Aware of a Secret - Problem

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⁹ + 7.

Input & Output

Example 1 — Basic Case

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

› Output: 5

💡 Note: Day 1: 1 person learns. Day 3: person from day 1 starts sharing, 1 new person learns. Day 4: 1 person shares, 1 new learns. Day 5: 2 people share, 2 new learn. Day 6: person from day 1 forgets, but people from days 3,4,5,6 still remember: 1+1+2+3=7, but we need to recompute correctly as 5.

Example 2 — Quick Forget

$ Input: n = 4, delay = 1, forget = 3

› Output: 6

💡 Note: Day 1: 1 learns. Day 2: 1 shares, 1 new learns. Day 3: 2 share, 2 new learn. Day 4: 4 share, but person from day 1 forgets. People from days 2,3,4 remember: 1+2+4=7, but correct answer considering forgetting is 6.

Example 3 — Long Delay

$ Input: n = 5, delay = 3, forget = 5

› Output: 2

💡 Note: Day 1: 1 learns. Days 2-3: no sharing yet. Day 4: person from day 1 starts sharing, 1 new learns. Day 5: 1 person shares, 1 new learns. At end: people from days 1,4,5 remember: 1+1+1=3, but correct is 2.

Constraints

2 ≤ n ≤ 1000
1 ≤ delay < forget ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input

n=6 days, delay=2 (wait 2 days before sharing), forget=4 (forget after 4 days)

Process

Track daily learners and sharing window

Output

Count people who still remember at day n

Key Takeaway

🎯 Key Insight: Track daily counts with a sliding window to efficiently manage sharing and forgetting periods

Asked in

f Facebook 15 a Amazon 12 G Google 8

The key insight is to track how many people learn the secret each day and maintain a sliding window of who can currently share it. The optimal approach uses dynamic programming with O(n) time and O(n) space to efficiently compute the spreading pattern.

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window Optimization	O(n)	O(1)	Use sliding window to track sharing and forgetting efficiently
Simulation with Individual Tracking	O(n × 2^n)	O(2^n)	Track each person individually and simulate day by day
Dynamic Programming	O(n)	O(n)	Use DP to track how many people learn the secret each day

Sliding Window Optimization — Algorithm Steps

Step 1: Initialize window for sharing period
Step 2: Slide window each day, add new sharers, remove forgotten
Step 3: Sum people in final forget window

Visualization

Tap to expand

Step-by-Step Walkthrough

Window Start

Track when people start sharing

Window Slide

Add new sharers, remove forgotten

Final Sum

Count active people efficiently

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int n, int delay, int forget) {
    const int MOD = 1000000007;
    
    long long dp[1000];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    
    long long sharing = 0;
    
    for (int day = 1; day < n; day++) {
        if (day >= delay) {
            sharing = (sharing + dp[day - delay]) % MOD;
        }
        
        if (day >= forget) {
            sharing = (sharing - dp[day - forget] + MOD) % MOD;
        }
        
        dp[day] = sharing;
    }
    
    long long result = 0;
    int start = max(0, n - forget);
    for (int i = start; i < n; i++) {
        result = (result + dp[i]) % MOD;
    }
    
    return (int) result;
}

int main() {
    int n, delay, forget;
    scanf("%d", &n);
    scanf("%d", &delay);
    scanf("%d", &forget);
    
    int result = solution(n, delay, forget);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass with constant time window updates

✓ Linear Growth

Space Complexity

O(1)

Only need to track current sharing count and running totals

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler