Count the Number of Ideal Arrays

// Accepted solution for LeetCode #2338: Count the Number of Ideal Arrays
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;
    }
}

// Accepted solution for LeetCode #2338: Count the Number of Ideal Arrays
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
}

# Accepted solution for LeetCode #2338: Count the Number of Ideal Arrays
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

// Accepted solution for LeetCode #2338: Count the Number of Ideal Arrays
/**
 * [2338] Count the Number of Ideal Arrays
 *
 * 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 from 1 to maxValue, for 0 <= i < n.
 * 	Every arr[i] is divisible by arr[i - 1], for 0 < i < n.
 *
 * Return the number of distinct ideal arrays of length n. Since the answer may be very large, return it modulo 10^9 + 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 2^nd 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 2^nd 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 <= 10^4
 * 	1 <= maxValue <= 10^4
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/count-the-number-of-ideal-arrays/
// discuss: https://leetcode.com/problems/count-the-number-of-ideal-arrays/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn ideal_arrays(n: i32, max_value: i32) -> i32 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_2338_example_1() {
        let n = 2;
        let max_value = 5;

        let result = 10;

        assert_eq!(Solution::ideal_arrays(n, max_value), result);
    }

    #[test]
    #[ignore]
    fn test_2338_example_2() {
        let n = 5;
        let max_value = 3;

        let result = 11;

        assert_eq!(Solution::ideal_arrays(n, max_value), result);
    }
}

// Accepted solution for LeetCode #2338: Count the Number of Ideal Arrays
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;
}