diff options
author | Jack Sangdahl <[email protected]> | 2025-06-16 23:08:55 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-16 23:08:55 -0600 |
commit | 403a31eb22ad406e0d49a72b867a057121828cc2 (patch) | |
tree | 0922f54579de6eb62f6746db1c92c3f744056017 | |
parent | ea099f773c6117b6d9b3b133b527d169ccbb2de0 (diff) | |
download | leetcode-403a31eb22ad406e0d49a72b867a057121828cc2.tar.gz leetcode-403a31eb22ad406e0d49a72b867a057121828cc2.zip |
-rw-r--r-- | count_num_arr_k_match_elem.c | 48 | ||||
-rw-r--r-- | count_num_arr_k_match_elem.py | 28 |
2 files changed, 76 insertions, 0 deletions
diff --git a/count_num_arr_k_match_elem.c b/count_num_arr_k_match_elem.c new file mode 100644 index 0000000..dd8838e --- /dev/null +++ b/count_num_arr_k_match_elem.c @@ -0,0 +1,48 @@ +// 3405. Count the Number of Arrays with K Matching Adjacent Elements +#include "leetcode.h" + +/* + * you are given three integers 'n', 'm', and 'k'. a good array 'arr' of size + * 'n' is defined as follows: each element in 'arr' is in inclusive range '[1, + * m]', and exactly 'k' indices 'i' where '1 <= i < n' satisfy the condition + * 'arr[i - 1] == arr[i]'. return the number of good arrays that can be formed. + * since the answer may be very large, return it modulo 10^9+7. + */ + +const int mod = 1e9 + 7; + +long long mult(long long n, long long m) { return (n * m) % mod; } + +long long power(long long n, long long m) { + long long res = 1, base = n; + while (m > 0) { + if (m & 1) + res = mult(res, base); + base = mult(base, base); + m >>= 1; + } + return res; +} + +long long inv(long long n) { return power(n, mod - 2); } + +long long factorial(long long n) { + long long res = 1; + for (long long i = 2; i <= n; ++i) + res = mult(res, i); + return res; +} + +long long combine(long long n, long long m) { + return mult(factorial(n), inv(mult(factorial(m), factorial(n - m)))); +} + +int countGoodArrays(int n, int m, int k) { + return mult(mult(combine(n - 1, n - 1 - k), m), power(m - 1, n - 1 - k)); +} + +int main() { + printf("%d\n", countGoodArrays(3, 2, 1)); // expect: 4 + printf("%d\n", countGoodArrays(4, 2, 2)); // expect: 6 + printf("%d\n", countGoodArrays(5, 2, 0)); // expect: 2 +} diff --git a/count_num_arr_k_match_elem.py b/count_num_arr_k_match_elem.py new file mode 100644 index 0000000..a3bc73f --- /dev/null +++ b/count_num_arr_k_match_elem.py @@ -0,0 +1,28 @@ +# 3405. Count the Number of Arrays with K Matching Adjacent Elements +from math import comb + +""" +you are given three integers 'n', 'm', and 'k'. a good array 'arr' of size +'n' is defined as follows: each element in 'arr' is in inclusive range '[1, +m]', and exactly 'k' indices 'i' where '1 <= i < n' satisfy the condition +'arr[i - 1] == arr[i]'. return the number of good arrays that can be formed. +since the answer may be very large, return it modulo 10^9+7. +""" + + +class Solution(object): + def countGoodArrays(self, n, m, k): + """ + :type n: int + :type m: int + :type k: int + :rtype: int + """ + return m * pow(m - 1, n - k - 1, mod := 1**9 + 7) * comb(n - 1, k) % mod + + +if __name__ == "__main__": + obj = Solution() + print(obj.countGoodArrays(n=3, m=2, k=1)) + print(obj.countGoodArrays(n=4, m=2, k=2)) + print(obj.countGoodArrays(n=5, m=2, k=0)) |