2327: Number-of-People-Aware-of-a-Secret
Medium

table of contents

attempt 1

My first solution was really stupid.

I initially treated the problem like a sliding window with two halves. The first half are people that discovered the secret delay days ago and are able to share the secret. The second half are people that recently discovered the secret and are NOT able to share the secret.

My algorithm uses a circular array to reduce space complexity, and iterates over the people who can share the secret to calculate how many new people learn it each day.

Exemplar table below:

DAY||1|2|3|4|4|5|6|7|8|
---|-------------------
   ||0 0|0 1|
   | 0|0 0|1 0| 
   | 0 0|0 1|0 1|
   | 0 0 0|1 0|1 1|
   | 0 0 0 1|0 1|1 1|
   | 0 0 0 1 0|1 1|1 2|

code

class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        int start = 1;
        vector<long long> days(forget+1, 0);
        int size = days.size();
        days[forget-1] = 1;

        for (int i = 0; i < n-1; ++i) {
            long long sum = 0;
            int index = start;

            for (int j = 0; j < forget - delay; ++j) {
                sum = (sum + days[index]) % MOD;
                index = (index + 1) % size;
            }
            index = (index + delay - 1) % size;
            days[index] = sum;

            start = (start + 1) % size;
        }
        long long ans = 0;
        start = (size + start - 1) % size;
        for (int i = 0; i < forget; ++i) {
            ans = (ans + days[start]) % MOD;
            start = (start + 1) % size;
        }
        return ans;
    }
private:
    int MOD = 1e9+7;
};

complexity

attempt 2

My second attempt makes a lot more sense. Now, we have a dp array instead, and we let it keep track of how many people learn about the secret on a given day.

Initially, on day 1, exactly one person knows the secret so dp[1] = 1.

vector<long long> dp (n+1, 0);
dp[1] = 1;

Then we maintain a share variable to keep track of the number of people sharing the secret on a given day.

int share = 0;

Now, on each day, we update the share variable:

for (int i = 2; i <= n; ++i) {
    dp[i] = share = (share + dp[max(i - delay, 0)] - dp[max(i - forget, 0)] + MOD) % MOD;
}

Afterwards, we can simply go back, iterate through the last forget days and sum up all the values to get the ans.

int ans = 0;
for (int i = n - forget + 1; i <= n; ++i) {
    ans = (ans + dp[i]) % MOD;
}
return ans;

code

class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        vector<long long> dp (n+1, 0);
        dp[1] = 1;
        int share = 0;

        for (int i = 2; i <= n; ++i) {
            dp[i] = share = (share + dp[max(i - delay, 0)] - dp[max(i - forget, 0)] + MOD) % MOD;
        }

        int ans = 0;
        for (int i = n - forget + 1; i <= n; ++i) {
            ans = (ans + dp[i]) % MOD;
        }
        return ans;
    }
private:
    const int MOD = 1e9+7;
};

complexity

time taken