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 <= 104In #2338 Count the Number of Ideal Arrays, the goal is to count arrays of length n where each element divides the next and values are bounded by maxValue. A brute-force enumeration is infeasible due to exponential possibilities, so the key insight is to analyze the multiplicative structure of numbers.
One effective strategy uses number theory and combinatorics. For each possible ending value, factorize it into primes. The divisibility chain corresponds to distributing the exponent increases across positions in the array. This transforms the problem into a classic combinations with repetition scenario, often solved using the stars and bars technique. Precomputing binomial coefficients allows efficient counting.
Another perspective is to use dynamic programming over divisors, where states represent valid sequences ending with a particular value. However, combining prime factorization with combinatorics significantly reduces transitions.
By precomputing combinations and prime factorizations up to maxValue, the algorithm efficiently aggregates counts for all valid end values.
Time Complexity: roughly O(maxValue log maxValue) with preprocessing. Space Complexity: O(maxValue).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Combinatorics + Prime Factorization | O(maxValue log maxValue) | O(maxValue) |
| Dynamic Programming over Divisibility | O(maxValue * log maxValue) | O(maxValue) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Notice that an ideal array is non-decreasing.
Consider an alternative problem: where an ideal array must also be strictly increasing. Can you use DP to solve it?
Will combinatorics help to get an answer from the alternative problem to the actual problem?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like this are representative of advanced interview questions that combine dynamic programming, combinatorics, and number theory. While the exact problem may not always appear, similar counting and divisor-based DP patterns are common in top tech interviews.
Combinatorics helps model how prime exponents can increase across positions in a divisible sequence. Instead of building arrays directly, we count the number of ways to distribute exponent increments across n positions using binomial coefficients.
The optimal approach combines number theory with combinatorics. By factorizing each possible value and distributing prime exponents across array positions using combinations (stars and bars), we can count valid arrays efficiently without enumerating them.
Precomputed arrays for factorials or binomial coefficients are essential. Additionally, arrays for storing smallest prime factors or prime factorizations help efficiently process all values up to maxValue.