aboutsummaryrefslogtreecommitdiff
path: root/count_num_ideal_arr.py
blob: 69667111e153818b89d08f3c3af0e2e3959a1240 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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))