diff options
author | Jack Sangdahl <[email protected]> | 2025-04-21 20:16:07 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-04-21 20:16:07 -0600 |
commit | e452b865cbb2f6af0c97380721f009f9672ad432 (patch) | |
tree | 7c37c36062ed507225e841533720029fffb9d0fa | |
parent | ebb9933e94bf1beacf487b8a3f1915a0ba92edbc (diff) | |
download | leetcode-e452b865cbb2f6af0c97380721f009f9672ad432.tar.gz leetcode-e452b865cbb2f6af0c97380721f009f9672ad432.zip |
2338. count the number of ideal arrays
-rw-r--r-- | count_num_ideal_arr.c | 36 | ||||
-rw-r--r-- | count_num_ideal_arr.py | 38 |
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)) |