Watch 10 video solutions for Count the Number of Ideal Arrays, a hard level problem involving Math, Dynamic Programming, Combinatorics. This walkthrough by codestorywithMIK has 8,248 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
arr[i] is a value from 1 to maxValue, for 0 <= i < n.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 <= 1041 <= maxValue <= 104Problem Overview: Count how many arrays of length n you can build where every element is between 1 and maxValue, and each element divides the next (a[i] | a[i+1]). The divisibility constraint forms multiplicative chains, which means each valid array corresponds to repeatedly multiplying by factors.
Approach 1: Dynamic Programming on Multiples (Time: O(maxValue * log(maxValue) * L), Space: O(maxValue * L))
This method builds arrays by extending smaller valid sequences. Define dp[len][v] as the number of arrays of length len ending with value v. For each value v, iterate through its multiples (2v, 3v, ...) and update the next length. The divisibility rule holds automatically because every multiple of v is divisible by v. The maximum chain length L is small (about 14 when maxValue ≤ 10^4) because values grow multiplicatively. This keeps the DP manageable and avoids exploring impossible long chains.
Precomputing multiples lets transitions run quickly. Each step distributes counts from smaller numbers to their multiples. The final result sums the number of valid chains of all lengths and distributes them across the n positions using combinations. This approach highlights the structure of divisibility chains and fits naturally with dynamic programming.
Approach 2: Combinatorics with Sieve of Eratosthenes (Time: O(maxValue log maxValue), Space: O(maxValue))
The key insight: every ideal array corresponds to choosing a final value and distributing its prime factors across n positions. Factorize each value ≤ maxValue. If a value has prime factorization p1^e1 * p2^e2 * ..., each exponent represents how many multiplicative steps must appear across the array. The number of ways to distribute e identical increases across n positions equals C(n - 1 + e, e) (stars and bars).
Use the Sieve of Eratosthenes to precompute smallest prime factors and factorize every number quickly. For each exponent in the factorization, multiply the combinations. Sum the results for all values from 1 to maxValue. Precompute combinations with Pascal's triangle or factorial + modular inverse under modulo 1e9+7. This converts the divisibility chain problem into a pure combinatorics calculation.
Recommended for interviews: The combinatorial approach with prime factorization is the expected optimal solution. It reduces the problem to counting exponent distributions and runs in roughly O(maxValue log maxValue). Implementing the DP approach first shows understanding of the divisibility structure, but the combinatorial method demonstrates stronger algorithmic insight and is usually what interviewers look for in hard math problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming on Multiples | O(maxValue * log(maxValue) * L) | O(maxValue * L) | When exploring divisibility chains directly or deriving the combinatorial insight step by step |
| Combinatorics with Sieve of Eratosthenes | O(maxValue log maxValue) | O(maxValue) | Optimal solution for large constraints using prime factorization and combinations |