Count the Number of Ideal Arrays

HARD

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 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⁹ + 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⁴
1 <= maxValue <= 10⁴

Approaches

Checkout 3 different approaches to solve Count the Number of Ideal Arrays. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming on Length and Value

This approach uses dynamic programming where the state dp[i][j] represents the number of ideal arrays of length i that end with the value j. We build up the solution for length n by iteratively computing the results for lengths from 1 to n.

Algorithm

Define a 2D DP array dp[i][j] to store the number of ideal arrays of length i ending with value j.
The state transition is dp[i][j] = sum(dp[i-1][k]) for all k that are divisors of j.
The base case is dp[1][j] = 1 for all 1 <= j <= maxValue.
To optimize the transition, instead of finding divisors for each j, iterate through k from the previous state and add dp[i-1][k] to all its multiples m*k.
Since dp[i] only depends on dp[i-1], we can optimize space by using only two rows (or one) of the DP table.
The final answer is the sum of all dp[n][j] for j from 1 to maxValue.

We can define dp[i][j] as the number of ideal arrays of length i ending with value j.

Base Case: For an array of length 1, any value j from 1 to maxValue is valid. So, dp[1][j] = 1 for 1 <= j <= maxValue.
Recurrence Relation: For an ideal array of length i > 1 ending in j, say [a_0, ..., a_{i-2}, j], the previous element a_{i-2} must be a divisor of j. Thus, the number of such arrays is the sum of the counts of ideal arrays of length i-1 ending in any divisor of j. The recurrence is: dp[i][j] = sum(dp[i-1][k]) for all k such that k | j.
Optimization: A naive implementation of this recurrence would be too slow. Instead of iterating through divisors of j to pull values from dp[i-1], we can iterate through k from 1 to maxValue and add dp[i-1][k] to dp[i][j] for all multiples j of k. This is more efficient.
Space Optimization: Notice that dp[i] only depends on dp[i-1]. We can optimize space from O(n * maxValue) to O(maxValue) by using only two arrays, one for the previous state and one for the current state.
Final Answer: The total number of ideal arrays is the sum of dp[n][j] for all j from 1 to maxValue.

class Solution {
    public int idealArrays(int n, int maxValue) {
        long MOD = 1_000_000_007;
        long[] dp = new long[maxValue + 1];
        Arrays.fill(dp, 1);
        dp[0] = 0; // 0 is not a valid value

        for (int i = 2; i <= n; i++) {
            long[] newDp = new long[maxValue + 1];
            for (int k = 1; k <= maxValue; k++) {
                if (dp[k] == 0) continue;
                for (int j = k; j <= maxValue; j += k) {
                    newDp[j] = (newDp[j] + dp[k]) % MOD;
                }
            }
            dp = newDp;
        }

        long totalCount = 0;
        for (int j = 1; j <= maxValue; j++) {
            totalCount = (totalCount + dp[j]) % MOD;
        }

        return (int) totalCount;
    }
}

Complexity Analysis

Time Complexity: O(n * maxValue * log(maxValue)) The outer loop runs `n-1` times. The inner loops iterate through all numbers and their multiples up to `maxValue`. The complexity of the inner part is `sum_{k=1 to maxValue} (maxValue/k)`, which is `O(maxValue * log(maxValue))`. The total time is `O(n * maxValue * log(maxValue))`, which is too slow for the given constraints.Space Complexity: O(maxValue) We use an array of size `maxValue` to store the DP states for the current length, which dominates the space requirement.

Pros and Cons

Pros:

Conceptually simple and follows a standard DP pattern.
Space complexity is manageable.

Cons:

The time complexity is high, making it too slow for the given constraints.
It recomputes a lot of information in each step of the length i.

Code Solutions

Checking out 3 solutions in different languages for Count the Number of Ideal Arrays. Click on different languages to view the code.

class Solution {
private
  int[][] f;
private
  int[][] c;
private
  int n;
private
  int m;
private
  static final int MOD = (int)1 e9 + 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;
  }
}

Video Solution

Watch the video walkthrough for Count the Number of Ideal Arrays

Patterns:

MathDynamic ProgrammingCombinatoricsNumber Theory

Companies:

Infosys |