2338. Count the Number of Ideal Arrays
Description
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 <= 1041 <= maxValue <= 104
Solutions
Solution 1: Dynamic Programming
Let $f[i][j]$ represent the number of sequences ending with $i$ and consisting of $j$ distinct elements. The initial value is $f[i][1] = 1$.
Consider $n$ balls, which are eventually divided into $j$ parts. Using the "separator method," we can insert $j-1$ separators into the $n-1$ positions, and the number of combinations is $c_{n-1}^{j-1}$.
We can preprocess the combination numbers $c[i][j]$ using the recurrence relation $c[i][j] = c[i-1][j] + c[i-1][j-1]$. Specifically, when $j=0$, $c[i][j] = 1$.
The final answer is:
$$ \sum\limits_{i=1}^{k}\sum\limits_{j=1}^{\log_2 k + 1} f[i][j] \times c_{n-1}^{j-1} $$
where $k$ represents the maximum value of the array, i.e., $\textit{maxValue}$.
Time Complexity: $O(m \times \log^2 m)$
Space Complexity: $O(m \times \log m)$
Python3
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
Java
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;
}
}
C++
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;
}
};
Go
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
}
Solution 2
Python3
class Solution:
def idealArrays(self, n: int, maxValue: int) -> int:
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
f = [[0] * 16 for _ in range(maxValue + 1)]
for i in range(1, maxValue + 1):
f[i][1] = 1
for j in range(1, 15):
for i in range(1, maxValue + 1):
k = 2
while k * i <= maxValue:
f[k * i][j + 1] = (f[k * i][j + 1] + f[i][j]) % mod
k += 1
ans = 0
for i in range(1, maxValue + 1):
for j in range(1, 16):
ans = (ans + f[i][j] * c[-1][j - 1]) % mod
return ans
Java
class Solution {
public int idealArrays(int n, int maxValue) {
final int mod = (int) 1e9 + 7;
int[][] 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;
}
}
long[][] f = new long[maxValue + 1][16];
for (int i = 1; i <= maxValue; ++i) {
f[i][1] = 1;
}
for (int j = 1; j < 15; ++j) {
for (int i = 1; i <= maxValue; ++i) {
int k = 2;
for (; k * i <= maxValue; ++k) {
f[k * i][j + 1] = (f[k * i][j + 1] + f[i][j]) % mod;
}
}
}
long ans = 0;
for (int i = 1; i <= maxValue; ++i) {
for (int j = 1; j < 16; ++j) {
ans = (ans + f[i][j] * c[n - 1][j - 1]) % mod;
}
}
return (int) ans;
}
}
C++
class Solution {
public:
int idealArrays(int n, int maxValue) {
const int mod = 1e9 + 7;
vector<vector<int>> c(n, vector<int>(16));
for (int i = 0; i < n; ++i) {
for (int 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;
}
}
}
vector<vector<long long>> f(maxValue + 1, vector<long long>(16));
for (int i = 1; i <= maxValue; ++i) {
f[i][1] = 1;
}
for (int j = 1; j < 15; ++j) {
for (int i = 1; i <= maxValue; ++i) {
for (int k = 2; k * i <= maxValue; ++k) {
f[k * i][j + 1] = (f[k * i][j + 1] + f[i][j]) % mod;
}
}
}
long long ans = 0;
for (int i = 1; i <= maxValue; ++i) {
for (int j = 1; j < 16; ++j) {
ans = (ans + f[i][j] * c[n - 1][j - 1]) % mod;
}
}
return ans;
}
};
Go
func idealArrays(n int, maxValue int) (ans int) {
const mod = int(1e9 + 7)
c := make([][]int, n)
for i := 0; i < n; i++ {
c[i] = make([]int, 16)
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
}
}
}
f := make([][16]int, maxValue+1)
for i := 1; i <= maxValue; i++ {
f[i][1] = 1
}
for j := 1; j < 15; j++ {
for i := 1; i <= maxValue; i++ {
for k := 2; k*i <= maxValue; k++ {
f[k*i][j+1] = (f[k*i][j+1] + f[i][j]) % mod
}
}
}
for i := 1; i <= maxValue; i++ {
for j := 1; j < 16; j++ {
ans = (ans + f[i][j]*c[n-1][j-1]) % mod
}
}
return
}
TypeScript
function idealArrays(n: number, maxValue: number): number {
const mod = 1e9 + 7;
const c: number[][] = Array.from({ length: n }, () => Array(16).fill(0));
for (let i = 0; i < n; i++) {
for (let 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;
}
}
}
const f: number[][] = Array.from({ length: maxValue + 1 }, () => Array(16).fill(0));
for (let i = 1; i <= maxValue; i++) {
f[i][1] = 1;
}
for (let j = 1; j < 15; j++) {
for (let i = 1; i <= maxValue; i++) {
for (let k = 2; k * i <= maxValue; k++) {
f[k * i][j + 1] = (f[k * i][j + 1] + f[i][j]) % mod;
}
}
}
let ans = 0;
for (let i = 1; i <= maxValue; i++) {
for (let j = 1; j < 16; j++) {
ans = (ans + f[i][j] * c[n - 1][j - 1]) % mod;
}
}
return ans;
}