Count the Number of Ideal Arrays

Hard

#2130Time: 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.1 company

Patterns

Math Dynamic Programming Combinatorics Number Theory

Companies

Infosys

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1class Solution {2    public int idealArrays(int n, int maxValue) {3        long MOD = 1_000_000_007;4        long[] dp = new long[maxValue + 1];5        Arrays.fill(dp, 1);6        dp[0] = 0; // 0 is not a valid value7 8        for (int i = 2; i <= n; i++) {9            long[] newDp = new long[maxValue + 1];10            for (int k = 1; k <= maxValue; k++) {11                if (dp[k] == 0) continue;12                for (int j = k; j <= maxValue; j += k) {13                    newDp[j] = (newDp[j] + dp[k]) % MOD;14                }15            }16            dp = newDp;17        }18 19        long totalCount = 0;20        for (int j = 1; j <= maxValue; j++) {21            totalCount = (totalCount + dp[j]) % MOD;22        }23 24        return (int) totalCount;25    }26}

Complexity

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.

Trade-offs

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.

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.

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

Walkthrough

The core idea is to count ideal arrays based on the number of distinct values they contain.

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

1class Solution {2    long MOD = 1_000_000_007;3    long[][] C;4 5    public int idealArrays(int n, int maxValue) {6        // Precompute combinations C(n, k)7        C = new long[n + 1][15];8        for (int i = 0; i <= n; i++) {9            C[i][0] = 1;10            for (int j = 1; j <= Math.min(i, 14); j++) {11                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;12            }13        }14 15        long[] dp = new long[maxValue + 1];16        Arrays.fill(dp, 1);17        dp[0] = 0;18 19        long totalAns = maxValue; // For k=1, ways[1] = maxValue, C(n-1, 0) = 120 21        for (int k = 2; k <= Math.min(n, 14); k++) {22            long[] newDp = new long[maxValue + 1];23            long ways_k = 0;24            for (int u = 1; u <= maxValue; u++) {25                if (dp[u] == 0) continue;26                for (int v = 2 * u; v <= maxValue; v += u) {27                    newDp[v] = (newDp[v] + dp[u]) % MOD;28                }29            }30            dp = newDp;31            for (long count : dp) {32                ways_k = (ways_k + count) % MOD;33            }34            if (ways_k == 0) break;35            totalAns = (totalAns + ways_k * C[n - 1][k - 1]) % MOD;36        }37 38        return (int) totalAns;39    }40}

Complexity

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)`.

Trade-offs

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.

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.

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.

Walkthrough

This method decouples the problem by considering the prime factorization of the array elements.

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}).
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).
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).
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.

1class Solution {2    long MOD = 1_000_000_007;3    long[] fact;4    long[] invFact;5 6    public int idealArrays(int n, int maxValue) {7        int limit = n + maxValue;8        fact = new long[limit];9        invFact = new long[limit];10        fact[0] = 1;11        invFact[0] = 1;12        for (int i = 1; i < limit; i++) {13            fact[i] = (fact[i - 1] * i) % MOD;14            invFact[i] = power(fact[i], MOD - 2);15        }16 17        int[] spf = new int[maxValue + 1];18        for (int i = 2; i <= maxValue; i++) {19            if (spf[i] == 0) {20                spf[i] = i;21                for (long j = (long)i * i; j <= maxValue; j += i) {22                    if (spf[(int)j] == 0) {23                        spf[(int)j] = i;24                    }25                }26            }27        }28 29        long totalAns = 0;30        for (int v = 1; v <= maxValue; v++) {31            long ways_v = 1;32            int temp_v = v;33            while (temp_v > 1) {34                int p = spf[temp_v];35                int count = 0;36                while (temp_v % p == 0) {37                    count++;38                    temp_v /= p;39                }40                ways_v = (ways_v * nCr(count + n - 1, n - 1)) % MOD;41            }42            totalAns = (totalAns + ways_v) % MOD;43        }44 45        return (int) totalAns;46    }47 48    private long nCr(int N, int R) {49        if (R < 0 || R > N) return 0;50        return (((fact[N] * invFact[R]) % MOD) * invFact[N - R]) % MOD;51    }52 53    private long power(long base, long exp) {54        long res = 1;55        base %= MOD;56        while (exp > 0) {57            if (exp % 2 == 1) res = (res * base) % MOD;58            base = (base * base) % MOD;59            exp /= 2;60        }61        return res;62    }63}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  int[][] f;4private5  int[][] c;6private7  int n;8private9  int m;10private11  static final int MOD = (int)1 e9 + 7;12public13  int idealArrays(int n, int maxValue) {14    this.n = n;15    this.m = maxValue;16    this.f = new int[maxValue + 1][16];17    for (int[] row : f) {18      Arrays.fill(row, -1);19    }20    c = new int[n][16];21    for (int i = 0; i < n; ++i) {22      for (int j = 0; j <= i && j < 16; ++j) {23        c[i][j] = j == 0 ? 1 : (c[i - 1][j] + c[i - 1][j - 1]) % MOD;24      }25    }26    int ans = 0;27    for (int i = 1; i <= m; ++i) {28      ans = (ans + dfs(i, 1)) % MOD;29    }30    return ans;31  }32private33  int dfs(int i, int cnt) {34    if (f[i][cnt] != -1) {35      return f[i][cnt];36    }37    int res = c[n - 1][cnt - 1];38    if (cnt < n) {39      for (int k = 2; k * i <= m; ++k) {40        res = (res + dfs(k * i, cnt + 1)) % MOD;41      }42    }43    f[i][cnt] = res;44    return res;45  }46}

1class Solution {2public:3  int m, n;4  const int mod = 1e9 + 7;5  vector<vector<int>> f;6  vector<vector<int>> c;7  int idealArrays(int n, int maxValue) {8    this->m = maxValue;9    this->n = n;10    f.assign(maxValue + 1, vector<int>(16, -1));11    c.assign(n, vector<int>(16, 0));12    for (int i = 0; i < n; ++i)13      for (int j = 0; j <= i && j < 16; ++j)14        c[i][j] = !j ? 1 : (c[i - 1][j] + c[i - 1][j - 1]) % mod;15    int ans = 0;16    for (int i = 1; i <= m; ++i)17      ans = (ans + dfs(i, 1)) % mod;18    return ans;19  }20  int dfs(int i, int cnt) {21    if (f[i][cnt] != -1)22      return f[i][cnt];23    int res = c[n - 1][cnt - 1];24    if (cnt < n)25      for (int k = 2; k * i <= m; ++k)26        res = (res + dfs(k * i, cnt + 1)) % mod;27    f[i][cnt] = res;28    return res;29  }30};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  int[][] f;4private5  int[][] c;6private7  int n;8private9  int m;10private11  static final int MOD = (int)1 e9 + 7;12public13  int idealArrays(int n, int maxValue) {14    this.n = n;15    this.m = maxValue;16    this.f = new int[maxValue + 1][16];17    for (int[] row : f) {18      Arrays.fill(row, -1);19    }20    c = new int[n][16];21    for (int i = 0; i < n; ++i) {22      for (int j = 0; j <= i && j < 16; ++j) {23        c[i][j] = j == 0 ? 1 : (c[i - 1][j] + c[i - 1][j - 1]) % MOD;24      }25    }26    int ans = 0;27    for (int i = 1; i <= m; ++i) {28      ans = (ans + dfs(i, 1)) % MOD;29    }30    return ans;31  }32private33  int dfs(int i, int cnt) {34    if (f[i][cnt] != -1) {35      return f[i][cnt];36    }37    int res = c[n - 1][cnt - 1];38    if (cnt < n) {39      for (int k = 2; k * i <= m; ++k) {40        res = (res + dfs(k * i, cnt + 1)) % MOD;41      }42    }43    f[i][cnt] = res;44    return res;45  }46}

1class Solution {2public:3  int m, n;4  const int mod = 1e9 + 7;5  vector<vector<int>> f;6  vector<vector<int>> c;7  int idealArrays(int n, int maxValue) {8    this->m = maxValue;9    this->n = n;10    f.assign(maxValue + 1, vector<int>(16, -1));11    c.assign(n, vector<int>(16, 0));12    for (int i = 0; i < n; ++i)13      for (int j = 0; j <= i && j < 16; ++j)14        c[i][j] = !j ? 1 : (c[i - 1][j] + c[i - 1][j - 1]) % mod;15    int ans = 0;16    for (int i = 1; i <= m; ++i)17      ans = (ans + dfs(i, 1)) % mod;18    return ans;19  }20  int dfs(int i, int cnt) {21    if (f[i][cnt] != -1)22      return f[i][cnt];23    int res = c[n - 1][cnt - 1];24    if (cnt < n)25      for (int k = 2; k * i <= m; ++k)26        res = (res + dfs(k * i, cnt + 1)) % mod;27    f[i][cnt] = res;28    return res;29  }30};

1class Solution:2    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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.