diff options
author | Jack Sangdahl <[email protected]> | 2025-09-08 21:30:40 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-08 21:30:40 -0600 |
commit | d17d14d45956ea9af8f75e23181d708e4f76979f (patch) | |
tree | 7f2a297eb9ab9aab5873bdc2781704d1c63651d5 | |
parent | 8c1fa0daec183d897b8a749b405b83ba91d42842 (diff) | |
download | leetcode-d17d14d45956ea9af8f75e23181d708e4f76979f.tar.gz leetcode-d17d14d45956ea9af8f75e23181d708e4f76979f.zip |
2327. number of people aware of a secret
-rw-r--r-- | num_people_aware_secret.c | 32 | ||||
-rw-r--r-- | num_people_aware_secret.py | 35 |
2 files changed, 67 insertions, 0 deletions
diff --git a/num_people_aware_secret.c b/num_people_aware_secret.c new file mode 100644 index 0000000..d9a09d2 --- /dev/null +++ b/num_people_aware_secret.c @@ -0,0 +1,32 @@ +// 2327. Number of People Aware of a Secret +#include "leetcode.h" + +/* + * on day 1, one person discovers decret. 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 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. + */ + +int peopleAwareOfSecret(int n, int delay, int forget) { + long *dp = (long *)malloc((n + 1) * sizeof(int)); + dp[1] = 1; + int share = 0, mod = 1e9 + 7, ans = 0; + for (int i = 2; i <= n; ++i) + dp[i] = share = (share + dp[(int)fmax(i - delay, 0)] - + dp[(int)fmax(i - forget, 0)] + mod) % + mod; + for (int i = n - forget + 1; i <= n; ++i) + ans = (ans + dp[i]) % mod; + free(dp); + return ans; +} + +int main() { + printf("%d\n", peopleAwareOfSecret(6, 2, 4)); // expect: 5 + printf("%d\n", peopleAwareOfSecret(4, 1, 3)); // expect: 6 +} diff --git a/num_people_aware_secret.py b/num_people_aware_secret.py new file mode 100644 index 0000000..8b13fea --- /dev/null +++ b/num_people_aware_secret.py @@ -0,0 +1,35 @@ +# 2327. Number of People Aware of a Secret + +""" +on day 1, one person discovers decret. 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 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. +""" + + +class Solution(object): + def peopleAwareOfSecret(self, n, delay, forget): + """ + :type n: int + :type delay: int + :type forget: int + :rtype: int + """ + dp = [1] + [0] * forget + share, mod = 0, 10**9 + 7 + for i in range(1, n): + dp[i % forget] = share = ( + share + dp[(i - delay) % forget] - dp[i % forget] + ) % forget + return sum(dp) % mod + + +if __name__ == "__main__": + obj = Solution() + print(obj.peopleAwareOfSecret(6, 2, 4)) + print(obj.peopleAwareOfSecret(4, 1, 3)) |