aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-21 20:16:07 -0600
committerJack Sangdahl <[email protected]>2025-04-21 20:16:07 -0600
commite452b865cbb2f6af0c97380721f009f9672ad432 (patch)
tree7c37c36062ed507225e841533720029fffb9d0fa
parentebb9933e94bf1beacf487b8a3f1915a0ba92edbc (diff)
downloadleetcode-e452b865cbb2f6af0c97380721f009f9672ad432.tar.gz
leetcode-e452b865cbb2f6af0c97380721f009f9672ad432.zip
2338. count the number of ideal arrays
-rw-r--r--count_num_ideal_arr.c36
-rw-r--r--count_num_ideal_arr.py38
2 files changed, 74 insertions, 0 deletions
diff --git a/count_num_ideal_arr.c b/count_num_ideal_arr.c
new file mode 100644
index 0000000..298b1da
--- /dev/null
+++ b/count_num_ideal_arr.c
@@ -0,0 +1,36 @@
+// 2338. Count the Number of Ideal Arrays
+#include "leetcode.h"
+
+/*
+ * you are given two integers 'n' and 'maxValue' which are used to describe an
+ * ideal array. a 0-indexed integer array 'arr' of length 'n' is considered
+ * ideal if the following conditions hold true: every 'arr[i]' is a value from 1
+ * to 'maxValue' for '0 <= i < n', and every 'arr[i]' is divisble by 'arr[i -
+ * 1]'. return the number of distinct ideal arrays of length 'n'. since the
+ * answer may be very large, return it modulo 10^9+7.
+ */
+
+int idealArrays(int n, int maxValue) {
+ int cmb[10001][14] = {1}, cnt[10001][14] = {}, mod = 1e9 + 7;
+ if (!cmb[1][1]) {
+ for (int i = 1; i <= 10000; ++i)
+ for (int j = 0; j < 14; ++j)
+ cmb[i][j] = !j ? 1 : (cmb[i - 1][j - 1] + cmb[i - 1][j]) % mod;
+ for (int i = 1; i <= 10000; ++i) {
+ ++cnt[i][0];
+ for (int j = 2 * i; j <= 10000; j += i)
+ for (int k = 0; cnt[i][k]; ++k)
+ cnt[j][k + 1] += cnt[i][k];
+ }
+ }
+ int ans = 0;
+ for (int i = 1; i <= maxValue; ++i)
+ for (int j = 0; j < fmin(14, n) && cnt[i][j]; ++j)
+ ans = (1LL * cnt[i][j] * cmb[n - 1][j] + ans) % mod;
+ return ans;
+}
+
+int main() {
+ printf("%d\n", idealArrays(2, 5)); // expect: 10
+ printf("%d\n", idealArrays(5, 3)); // expect: 11
+}
diff --git a/count_num_ideal_arr.py b/count_num_ideal_arr.py
new file mode 100644
index 0000000..6966711
--- /dev/null
+++ b/count_num_ideal_arr.py
@@ -0,0 +1,38 @@
+# 2338. Count the Number of Ideal Arrays
+from collections import Counter
+from math import comb
+
+"""
+you are given two integers 'n' and 'maxValue' which are used to describe an
+ideal array. a 0-indexed integer array 'arr' of length 'n' is considered
+ideal if the following conditions hold true: every 'arr[i]' is a value from 1
+to 'maxValue' for '0 <= i < n', and every 'arr[i]' is divisble by 'arr[i -
+1]'. return the number of distinct ideal arrays of length 'n'. since the
+answer may be very large, return it modulo 10^9+7.
+"""
+
+
+class Solution(object):
+ def idealArrays(self, n, maxValue):
+ """
+ :type n: int
+ :type maxValue: int
+ :rtype: int
+ """
+ ans = maxValue
+ freq = {i: 1 for i in range(1, maxValue + 1)}
+ for i in range(1, n):
+ tmp = Counter()
+ for j in freq:
+ for k in range(2, maxValue // j + 1):
+ ans += comb(n - 1, i) * freq[j]
+ tmp[k * j] += freq[j]
+ freq = tmp
+ ans %= 10**9 + 7
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.idealArrays(n=2, maxValue=5))
+ print(obj.idealArrays(n=5, maxValue=3))