Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2338.html
2338. Count the Number of Ideal Arrays
- Difficulty: Hard.
- Related Topics: Math, Dynamic Programming, Combinatorics, Number Theory.
- Similar Questions: Count Ways to Make Array With Product.
Problem
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:
-
Every
arr[i]is a value from1tomaxValue, for0 <= i < n. -
Every
arr[i]is divisible byarr[i - 1], for0 < i < n.
Return the number of **distinct ideal arrays of length **n. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: n = 2, maxValue = 5
Output: 10
Explanation: The following are the possible ideal arrays:
- Arrays starting with the value 1 (5 arrays): [1,1], [1,2], [1,3], [1,4], [1,5]
- Arrays starting with the value 2 (2 arrays): [2,2], [2,4]
- Arrays starting with the value 3 (1 array): [3,3]
- Arrays starting with the value 4 (1 array): [4,4]
- Arrays starting with the value 5 (1 array): [5,5]
There are a total of 5 + 2 + 1 + 1 + 1 = 10 distinct ideal arrays.
Example 2:
Input: n = 5, maxValue = 3
Output: 11
Explanation: The following are the possible ideal arrays:
- Arrays starting with the value 1 (9 arrays):
- With no other distinct values (1 array): [1,1,1,1,1]
- With 2nd distinct value 2 (4 arrays): [1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
- With 2nd distinct value 3 (4 arrays): [1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
- Arrays starting with the value 2 (1 array): [2,2,2,2,2]
- Arrays starting with the value 3 (1 array): [3,3,3,3,3]
There are a total of 9 + 1 + 1 = 11 distinct ideal arrays.
Constraints:
-
2 <= n <= 104 -
1 <= maxValue <= 104
Solution
-
class Solution { public int idealArrays(int n, int maxValue) { int mod = (int) (1e9 + 7); int maxDistinct = (int) (Math.log(maxValue) / Math.log(2)) + 1; int[][] dp = new int[maxDistinct + 1][maxValue + 1]; Arrays.fill(dp[1], 1); dp[1][0] = 0; for (int i = 2; i <= maxDistinct; i++) { for (int j = 1; j <= maxValue; j++) { for (int k = 2; j * k <= maxValue && dp[i - 1][j * k] != 0; k++) { dp[i][j] += dp[i - 1][j * k]; } } } int[] sum = new int[maxDistinct + 1]; for (int i = 1; i <= maxDistinct; i++) { sum[i] = Arrays.stream(dp[i]).sum(); } long[] invs = new long[Math.min(n, maxDistinct) + 1]; invs[1] = 1; for (int i = 2; i < invs.length; i++) { invs[i] = mod - mod / i * invs[mod % i] % mod; } long result = maxValue; long comb = (long) n - 1; for (int i = 2; i <= maxDistinct && i <= n; i++) { result += (sum[i] * comb) % mod; comb *= n - i; comb %= mod; comb *= invs[i]; comb %= mod; } return (int) (result % mod); } } ############ class Solution { private int[][] f; private int[][] c; private int n; private int m; private static final int MOD = (int) 1e9 + 7; public int idealArrays(int n, int maxValue) { this.n = n; this.m = maxValue; this.f = new int[maxValue + 1][16]; for (int[] row : f) { Arrays.fill(row, -1); } c = new int[n][16]; for (int i = 0; i < n; ++i) { for (int j = 0; j <= i && j < 16; ++j) { c[i][j] = j == 0 ? 1 : (c[i - 1][j] + c[i - 1][j - 1]) % MOD; } } int ans = 0; for (int i = 1; i <= m; ++i) { ans = (ans + dfs(i, 1)) % MOD; } return ans; } private int dfs(int i, int cnt) { if (f[i][cnt] != -1) { return f[i][cnt]; } int res = c[n - 1][cnt - 1]; if (cnt < n) { for (int k = 2; k * i <= m; ++k) { res = (res + dfs(k * i, cnt + 1)) % MOD; } } f[i][cnt] = res; return res; } } -
class Solution: def idealArrays(self, n: int, maxValue: int) -> int: @cache def dfs(i, cnt): res = c[-1][cnt - 1] if cnt < n: k = 2 while k * i <= maxValue: res = (res + dfs(k * i, cnt + 1)) % mod k += 1 return res c = [[0] * 16 for _ in range(n)] mod = 10**9 + 7 for i in range(n): for j in range(min(16, i + 1)): c[i][j] = 1 if j == 0 else (c[i - 1][j] + c[i - 1][j - 1]) % mod ans = 0 for i in range(1, maxValue + 1): ans = (ans + dfs(i, 1)) % mod return ans -
class Solution { public: int m, n; const int mod = 1e9 + 7; vector<vector<int>> f; vector<vector<int>> c; int idealArrays(int n, int maxValue) { this->m = maxValue; this->n = n; f.assign(maxValue + 1, vector<int>(16, -1)); c.assign(n, vector<int>(16, 0)); for (int i = 0; i < n; ++i) for (int j = 0; j <= i && j < 16; ++j) c[i][j] = !j ? 1 : (c[i - 1][j] + c[i - 1][j - 1]) % mod; int ans = 0; for (int i = 1; i <= m; ++i) ans = (ans + dfs(i, 1)) % mod; return ans; } int dfs(int i, int cnt) { if (f[i][cnt] != -1) return f[i][cnt]; int res = c[n - 1][cnt - 1]; if (cnt < n) for (int k = 2; k * i <= m; ++k) res = (res + dfs(k * i, cnt + 1)) % mod; f[i][cnt] = res; return res; } }; -
func idealArrays(n int, maxValue int) int { mod := int(1e9) + 7 m := maxValue c := make([][]int, n) f := make([][]int, m+1) for i := range c { c[i] = make([]int, 16) } for i := range f { f[i] = make([]int, 16) for j := range f[i] { f[i][j] = -1 } } var dfs func(int, int) int dfs = func(i, cnt int) int { if f[i][cnt] != -1 { return f[i][cnt] } res := c[n-1][cnt-1] if cnt < n { for k := 2; k*i <= m; k++ { res = (res + dfs(k*i, cnt+1)) % mod } } f[i][cnt] = res return res } for i := 0; i < n; i++ { for j := 0; j <= i && j < 16; j++ { if j == 0 { c[i][j] = 1 } else { c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod } } } ans := 0 for i := 1; i <= m; i++ { ans = (ans + dfs(i, 1)) % mod } return ans }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).