Count the Number of Ideal Arrays
HardPrompt
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 from1tomaxValue, for0 <= i < n. - Every
arr[i]is divisible byarr[i - 1], for0 < 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 <= 1041 <= maxValue <= 104
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 lengthiending with valuej. - The state transition is
dp[i][j] = sum(dp[i-1][k])for allkthat are divisors ofj. - The base case is
dp[1][j] = 1for all1 <= j <= maxValue. - To optimize the transition, instead of finding divisors for each
j, iterate throughkfrom the previous state and adddp[i-1][k]to all its multiplesm*k. - Since
dp[i]only depends ondp[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]forjfrom 1 tomaxValue.
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
jfrom 1 tomaxValueis valid. So,dp[1][j] = 1for1 <= j <= maxValue. -
Recurrence Relation: For an ideal array of length
i > 1ending inj, say[a_0, ..., a_{i-2}, j], the previous elementa_{i-2}must be a divisor ofj. Thus, the number of such arrays is the sum of the counts of ideal arrays of lengthi-1ending in any divisor ofj. The recurrence is:dp[i][j] = sum(dp[i-1][k])for allksuch thatk | j. -
Optimization: A naive implementation of this recurrence would be too slow. Instead of iterating through divisors of
jto pull values fromdp[i-1], we can iterate throughkfrom 1 tomaxValueand adddp[i-1][k]todp[i][j]for all multiplesjofk. This is more efficient. -
Space Optimization: Notice that
dp[i]only depends ondp[i-1]. We can optimize space fromO(n * maxValue)toO(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 alljfrom 1 tomaxValue.
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
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.
Solutions
Solution
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 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.