{x}
blog image

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

Solution Explanation

This problem asks to count the number of "ideal arrays" of length n where each element is between 1 and maxValue, and each element is divisible by the previous one. The solution involves dynamic programming and combinatorics.

Approach:

Both solutions leverage dynamic programming to efficiently count ideal arrays. The core idea is to build up solutions from smaller subproblems.

Solution 1 (Top-Down DP):

This solution uses a recursive top-down approach with memoization (@cache in Python, f[][] in Java/C++/Go).

  1. Combinatorics (Pre-computation): It pre-computes binomial coefficients (c[][]) which are needed to count the number of ways to choose distinct values for the array. The binomial coefficient C(n, k) represents the number of ways to choose k distinct values from a set of n values. This is a crucial optimization to avoid redundant calculations in the DP step. We only need to calculate a limited number of binomial coefficients (up to 15 in this case, as this will cover a good range of cases and increase time efficiency)

  2. Recursive DP (dfs function): The dfs(i, cnt) function counts ideal arrays starting with the value i and having cnt distinct values so far.

    • Base Case: If cnt == n, it means we've filled the array, so we return the corresponding binomial coefficient c[n-1][cnt-1].
    • Recursive Step: If cnt < n, it iterates through multiples of i ( k * i) up to maxValue. For each multiple, it recursively calls dfs to count ideal arrays that extend the current array with this multiple. The results from the recursive calls are summed up and returned (modulo 10^9 + 7).

  3. Main Loop: The main loop iterates through all possible starting values from 1 to maxValue, calling dfs for each starting value and summing the results to obtain the final count of ideal arrays.

Solution 2 (Bottom-Up DP):

This solution uses a bottom-up iterative approach.

  1. Combinatorics (Pre-computation): Similar to Solution 1, it pre-computes binomial coefficients (c[][]).

  2. Iterative DP (dp[][]): The dp[i][j] array stores the count of ideal arrays with j distinct values and ending in the value i.

    • Initialization: dp[i][1] = 1 for all i (arrays of length 1).
    • Iteration: It iterates through the number of distinct values (j) and then through all possible ending values (i). For each i, it considers all possible previous values (p) that divide i and updates dp[i][j] by summing the counts from dp[p][j-1].

  3. Final Calculation: After the DP iteration, it iterates through dp and sums the counts, multiplying each count by the corresponding binomial coefficient to account for the number of ways to arrange the distinct values in the array.

Time Complexity Analysis:

  • Solution 1: The time complexity is dominated by the recursive DP calls. In the worst case, the recursion tree could have a depth of n, and the branching factor is at most maxValue. However, due to memoization, each subproblem is solved only once. Therefore, the overall time complexity is approximately O(n * maxValue). The pre-computation of binomial coefficients is O(n^2).
  • Solution 2: The time complexity is O(maxValue^2 * n) because of the nested loops in the DP. The pre-computation of binomial coefficients is O(n^2).

Space Complexity Analysis:

  • Solution 1: O(n * maxValue) due to memoization in the dfs function.
  • Solution 2: O(maxValue * n) because of the DP table dp[][].

Both solutions achieve the same result, but Solution 2 might be slightly more efficient in practice because it avoids the overhead of recursion. However, the difference will be minor unless n and maxValue are extremely large. Solution 1 is perhaps easier to understand conceptually due to its clear recursive structure.