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.
The key idea is to use dynamic programming to count the number of ways to fill each position in the array. We use a DP table where dp[i][j] represents the number of ways to fill up to the i-th position in the array ending with value j. We initialize the first position and iteratively compute the subsequent positions considering the divisibility constraint.
This solution uses a 2D array dp to compute the count of ideal arrays. The outer loop on i goes through the length of the desired array, while the inner nested loops iterate over possible values in the array, tracking which values are divisible by each other to construct valid sequences.
The time complexity is O(n * maxValue^2) due to the nested loops. The space complexity is O(n * maxValue), as we store results for all positions and possible last values.
In this approach, we employ a mathematical strategy using combinatorics and the Sieve of Eratosthenes algorithm. By precomputing factors and valid sequences, we reduce the number of operations needed to determine valid ideal arrays.
This C implementation of the combinatorial approach calculates combinations efficiently, then uses a sieve-like update of valid ideal array counts. Each step leverages precomputed info for faster determination.
Time complexity is approximately O(n * maxValue * log(maxValue)), relying on multiplication instead of iteration per number.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming | The time complexity is |
| Combinatorial with Sieve of Eratosthenes | Time complexity is approximately |
| Default Approach | — |
| 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 |
Count the Number of Ideal Arrays | Detailed Explanation | Explained Maths | Leetcode 2338 | MIK • codestorywithMIK • 8,248 views views
Watch 9 more video solutions →Practice Count the Number of Ideal Arrays with our built-in code editor and test cases.
Practice on FleetCode