# Count the Number of Ideal Arrays
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-the-number-of-ideal-arrays)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-ideal-arrays
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
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`

# Approaches
## 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`.
**Time:** 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:** O(maxValue)
We use an array of size `maxValue` to store the DP states for the current length, which dominates the space requirement.
**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`.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Dynamic Programming on Number of Distinct Values
This approach observes that any ideal array is composed of a non-decreasing sequence of values. We can rephrase the problem as first choosing a sequence of `k` distinct values `d_1 < d_2 < ... < d_k` that satisfy the divisibility condition, and then arranging them into an `n`-length array. The number of distinct values `k` is small, which makes this approach more efficient.
**Time:** O(log(maxValue) * maxValue * log(maxValue))
The outer loop runs for `k` from 2 up to `min(n, ~log2(maxValue))`. The inner part to compute the next DP state takes `O(maxValue * log(maxValue))`. This makes the total time complexity better than the first approach. · **Space:** O(maxValue + n)
We need `O(maxValue)` for the DP array and `O(n * log(maxValue))` for the combinations table. Since `log(maxValue)` is small, this is effectively `O(maxValue + n)`.
**Pros:** Significantly more efficient than the previous approach for large `n`.; Leverages a key insight about the small number of distinct values.
**Cons:** The logic is more complex than the straightforward DP on length.; Still involves a `maxValue * log(maxValue)` computation in a loop.
### Explanation
The core idea is to count ideal arrays based on the number of distinct values they contain.

1.  **Combinatorial Insight:** An ideal array with `k` distinct values `d_1, d_2, ..., d_k` must have `d_1 < d_2 < ... < d_k` and `d_i | d_{i+1}`. The number of ways to place these `k` values into an array of length `n` is a stars-and-bars problem, equivalent to placing `k-1` dividers in `n-1` slots, which is `C(n-1, k-1)`.

2.  **Total Count Formula:** The total number of ideal arrays is `sum_{k=1 to n} ways[k] * C(n-1, k-1)`, where `ways[k]` is the number of valid sequences of `k` distinct values.

3.  **DP for `ways[k]`:** We can use dynamic programming to find `ways[k]`. Let `dp[v]` store the number of valid sequences of a certain length ending with value `v`. We can iterate on the length `k`.
    - For `k=1`, `dp[v] = 1` for all `v`. `ways[1] = maxValue`.
    - For `k > 1`, we compute a new `new_dp` array. `new_dp[v]` is the sum of `dp[u]` for all proper divisors `u` of `v`. This can be computed efficiently by iterating through `u` and adding `dp[u]` to its multiples `m*u` (where `m > 1`).

4.  **Bounded `k`:** The number of distinct values `k` is small. Since `d_i >= 2*d_{i-1}`, we have `d_k >= 2^(k-1)`. As `d_k <= maxValue`, `k-1 <= log2(maxValue)`, so `k` is at most `~14` for `maxValue=10^4`.

```java
class Solution {
    long MOD = 1_000_000_007;
    long[][] C;

    public int idealArrays(int n, int maxValue) {
        // Precompute combinations C(n, k)
        C = new long[n + 1][15];
        for (int i = 0; i <= n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= Math.min(i, 14); j++) {
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
            }
        }

        long[] dp = new long[maxValue + 1];
        Arrays.fill(dp, 1);
        dp[0] = 0;

        long totalAns = maxValue; // For k=1, ways[1] = maxValue, C(n-1, 0) = 1

        for (int k = 2; k <= Math.min(n, 14); k++) {
            long[] newDp = new long[maxValue + 1];
            long ways_k = 0;
            for (int u = 1; u <= maxValue; u++) {
                if (dp[u] == 0) continue;
                for (int v = 2 * u; v <= maxValue; v += u) {
                    newDp[v] = (newDp[v] + dp[u]) % MOD;
                }
            }
            dp = newDp;
            for (long count : dp) {
                ways_k = (ways_k + count) % MOD;
            }
            if (ways_k == 0) break;
            totalAns = (totalAns + ways_k * C[n - 1][k - 1]) % MOD;
        }

        return (int) totalAns;
    }
}
```
### Algorithm
- The problem can be reframed as: first, choose a sequence of `k` distinct values `d_1 < d_2 < ... < d_k` satisfying `d_i | d_{i+1}` and `d_k <= maxValue`. Second, arrange these `k` values into an `n`-length array.
- The number of ways to arrange `k` distinct values into an `n`-length ideal array is `C(n-1, k-1)`.
- The total count is `sum_{k=1 to n} (ways[k] * C(n-1, k-1))`, where `ways[k]` is the number of valid sequences of `k` distinct values.
- Use DP to find `ways[k]`. Let `dp[v]` be the number of valid sequences of the current length ending in `v`.
- Iterate `k` from 1 up to `min(n, log2(maxValue))`. In each iteration, compute the new `dp` array based on the previous one.
- The transition is: `new_dp[v] = sum(dp[u])` for all proper divisors `u` of `v`.
- Precompute combinations `C(n, k)`.

## Combinatorics with Prime Factorization
This is the most efficient approach, which relies on a combinatorial insight related to prime factorization. The divisibility constraint `a[i-1] | a[i]` can be analyzed independently for each prime factor's exponents. This transforms the problem of counting sequences of numbers into counting non-decreasing sequences of exponents for each prime, which has a direct combinatorial formula.
**Time:** O(maxValue * log(maxValue) + n)
The sieve precomputation takes `O(maxValue * log(log(maxValue)))`. Precomputing factorials takes `O(maxValue + n)`. The main loop runs from 1 to `maxValue`. Inside the loop, prime factorization using the SPF array takes `O(log v)`. The total time is dominated by the main loop, resulting in `O(maxValue * log(maxValue))`. The `+n` comes from factorial precomputation. · **Space:** O(maxValue + n)
We need `O(maxValue)` for the Sieve (SPF array) and `O(maxValue + n)` for precomputed factorials and their inverses.
**Pros:** Most efficient approach with the best time complexity.; Provides a closed-form formula for the number of arrays ending in a specific value.; Elegant solution based on number theory principles.
**Cons:** Requires knowledge of number theory concepts like prime factorization and modular arithmetic for combinations.; Implementation is more involved due to the need for a sieve and modular inverse calculations.
### Explanation
This method decouples the problem by considering the prime factorization of the array elements.

1.  **Decomposition by Prime Factors:** An ideal array `[a_0, a_1, ..., a_{n-1}]` satisfies `a_{i-1} | a_i`. This is equivalent to saying that for every prime `p`, the sequence of exponents of `p` in the prime factorization of the array elements is non-decreasing. That is, `exp_p(a_0) <= exp_p(a_1) <= ... <= exp_p(a_{n-1})`.

2.  **Counting for a Fixed End Value:** Let's count the number of ideal arrays of length `n` that end with a specific value `v`. Let the prime factorization of `v` be `p_1^{e_1} * p_2^{e_2} * ... * p_r^{e_r}`. For each prime `p_j`, we need to find the number of non-decreasing sequences of exponents of length `n`, `(exp_0, ..., exp_{n-1})`, such that `0 <= exp_0 <= ... <= exp_{n-1} = e_j`. This is equivalent to counting non-decreasing sequences of length `n-1` with elements from `{0, ..., e_j}`. Using stars and bars, the number of such sequences is `C(e_j + (n-1), n-1)`.

3.  **Total Ways for `v`:** Since the choice of exponent sequences for different primes are independent, we can multiply their counts. The number of ideal arrays ending in `v` is `product_{j=1 to r} C(e_j + n - 1, n - 1)`.

4.  **Algorithm:**
    - Precompute factorials and modular inverses to calculate `C(n, k)` in `O(1)`. The maximum value for `n` in `C(n,k)` will be `maxValue + n - 1` but we only need `C(a+n-1, n-1)` where `a` is an exponent, so `a <= log2(maxValue)`. The upper bound for combinations is `C(log2(maxValue) + n - 1, n - 1)`. We need factorials up to `n + maxValue`.
    - Use a sieve to find the Smallest Prime Factor (SPF) for all numbers up to `maxValue`.
    - Iterate `v` from 1 to `maxValue`. For each `v`, find its prime factorization using the SPF array. For each prime factor `p` with exponent `e`, calculate `C(e + n - 1, n - 1)` and multiply these results to get the ways for `v`.
    - Sum up the ways for all `v` to get the final answer.

```java
class Solution {
    long MOD = 1_000_000_007;
    long[] fact;
    long[] invFact;

    public int idealArrays(int n, int maxValue) {
        int limit = n + maxValue;
        fact = new long[limit];
        invFact = new long[limit];
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i < limit; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
            invFact[i] = power(fact[i], MOD - 2);
        }

        int[] spf = new int[maxValue + 1];
        for (int i = 2; i <= maxValue; i++) {
            if (spf[i] == 0) {
                spf[i] = i;
                for (long j = (long)i * i; j <= maxValue; j += i) {
                    if (spf[(int)j] == 0) {
                        spf[(int)j] = i;
                    }
                }
            }
        }

        long totalAns = 0;
        for (int v = 1; v <= maxValue; v++) {
            long ways_v = 1;
            int temp_v = v;
            while (temp_v > 1) {
                int p = spf[temp_v];
                int count = 0;
                while (temp_v % p == 0) {
                    count++;
                    temp_v /= p;
                }
                ways_v = (ways_v * nCr(count + n - 1, n - 1)) % MOD;
            }
            totalAns = (totalAns + ways_v) % MOD;
        }

        return (int) totalAns;
    }

    private long nCr(int N, int R) {
        if (R < 0 || R > N) return 0;
        return (((fact[N] * invFact[R]) % MOD) * invFact[N - R]) % MOD;
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
- The total number of ideal arrays is `sum_{v=1 to maxValue} (number of ideal arrays ending in v)`.
- The problem can be decoupled for each prime factor. For an array `[a_0, ..., a_{n-1}]` ending in `v`, the sequence of exponents of any prime `p` must be non-decreasing: `exp_p(a_0) <= ... <= exp_p(a_{n-1}) = exp_p(v)`.
- The number of such non-decreasing exponent sequences of length `n` for a prime `p` with final exponent `e_p` is `C(e_p + n - 1, n - 1)`.
- The total number of ways for a fixed `v` is the product of these counts over all its prime factors: `product_{p|v} C(exp_p(v) + n - 1, n - 1)`.
- Precompute factorials and their modular inverses to calculate combinations in `O(1)`.
- Use a sieve to precompute the Smallest Prime Factor (SPF) for all numbers up to `maxValue`.
- Iterate `v` from 1 to `maxValue`, find its prime factorization using the SPF array in `O(log v)` time, calculate the ways for `v`, and add to the total answer.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

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

```