aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--count_num_arr_k_match_elem.c48
-rw-r--r--count_num_arr_k_match_elem.py28
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))