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 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

Approach 01:

#include <vector>
using namespace std;

class Solution {
public:
    int idealArrays(int arrayLength, int maxValue) {
        const int maxSequenceLength = min(14, arrayLength);
        const vector<vector<int>> factorList = getFactors(maxValue);
        vector<vector<long>> dp(maxSequenceLength + 1, vector<long>(maxValue + 1));
        vector<vector<long>> combinationMemo(arrayLength, vector<long>(maxSequenceLength, -1));
        long totalCount = 0;

        for (int value = 1; value <= maxValue; ++value){
            dp[1][value] = 1;
        }
        for (int length = 2; length <= maxSequenceLength; ++length){
            for (int value = 1; value <= maxValue; ++value){
                for (const int factor : factorList[value]) {
                    dp[length][value] += dp[length - 1][factor];
                    dp[length][value] %= kMod;
                }
            }
        }

        for (int length = 1; length <= maxSequenceLength; ++length)
            for (int value = 1; value <= maxValue; ++value) {
                dp[length][0] += dp[length][value];
                dp[length][0] %= kMod;
            }

        for (int length = 1; length <= maxSequenceLength; ++length) {
            totalCount += dp[length][0] * computeCombination(arrayLength - 1, length - 1, combinationMemo);
            totalCount %= kMod;
        }

        return totalCount;
    }

private:
    static constexpr int kMod = 1'000'000'007;

    vector<vector<int>> getFactors(int maxValue) {
        vector<vector<int>> factorList(maxValue + 1);
        for (int divisor = 1; divisor <= maxValue; ++divisor){
            for (int multiple = divisor * 2; multiple <= maxValue; multiple += divisor){
                factorList[multiple].push_back(divisor);
            }
        }
        return factorList;
    }

    long computeCombination(int n, int k, vector<vector<long>>& memo) {
        if (k == 0 || n == k){
            return 1;
        }
        if (memo[n][k] != -1){
            return memo[n][k];
        }
        return memo[n][k] = (computeCombination(n - 1, k, memo) + computeCombination(n - 1, k - 1, memo)) % kMod;
    }
};

from typing import List

class Solution:
    MOD = 10**9 + 7

    def idealArrays(self, arrayLength: int, maxValue: int) -> int:
        maxSequenceLength = min(14, arrayLength)
        factorList = self.getFactors(maxValue)
        dp = [[0] * (maxValue + 1) for _ in range(maxSequenceLength + 1)]
        combinationMemo = [[-1] * maxSequenceLength for _ in range(arrayLength)]

        totalCount = 0

        for value in range(1, maxValue + 1):
            dp[1][value] = 1

        for length in range(2, maxSequenceLength + 1):
            for value in range(1, maxValue + 1):
                for factor in factorList[value]:
                    dp[length][value] += dp[length - 1][factor]
                    dp[length][value] %= self.MOD

        for length in range(1, maxSequenceLength + 1):
            dp[length][0] = sum(dp[length][1:]) % self.MOD

        for length in range(1, maxSequenceLength + 1):
            totalCount += dp[length][0] * self.computeCombination(arrayLength - 1, length - 1, combinationMemo)
            totalCount %= self.MOD

        return totalCount

    def getFactors(self, maxValue: int) -> List[List[int]]:
        factorList = [[] for _ in range(maxValue + 1)]
        for divisor in range(1, maxValue + 1):
            for multiple in range(divisor * 2, maxValue + 1, divisor):
                factorList[multiple].append(divisor)
        return factorList

    def computeCombination(self, n: int, k: int, memo: List[List[int]]) -> int:
        if k == 0 or n == k:
            return 1
        if memo[n][k] != -1:
            return memo[n][k]
        memo[n][k] = (self.computeCombination(n - 1, k, memo) + self.computeCombination(n - 1, k - 1, memo)) % self.MOD
        return memo[n][k]

Time Complexity:

• Factor List Generation:

  For every number up to maxValue, we store its divisors → \( O(m \log m) \), where \( m = \text{maxValue} \)

• DP Table Filling:

  The DP table has at most 14 rows (sequence lengths) and \( m \) columns. For each cell, we sum over its factors → \( O(14 \cdot m \log m) \)

• Combination Computation:

  Each combination is computed recursively and memoized. Total number of unique calls is \( O(n \cdot 14) \), where \( n = \text{arrayLength} \)

• Total Time Complexity:

  \( O(m \log m + n \cdot 14 + 14 \cdot m \log m) = O(m \log m + n) \)

Space Complexity:

• DP Table:

  We use a 2D table of size \( 15 \times (m + 1) \) → \( O(m) \)

• Factor List:

  Stores divisors for each number up to \( m \) → \( O(m \log m) \)

• Combination Memoization Table:

  Stores values for combinations up to \( n \times 14 \) → \( O(n) \)

• Total Space Complexity:

  \( O(m \log m + n) \)