diff options
Diffstat (limited to 'count_num_ideal_arr.py')
-rw-r--r-- | count_num_ideal_arr.py | 38 |
1 files changed, 38 insertions, 0 deletions
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)) |