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 <= 104The 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time complexity is approximately O(n * maxValue * log(maxValue)), relying on multiplication instead of iteration per number.
| Approach | Complexity |
|---|---|
| Dynamic Programming | The time complexity is |
| Combinatorial with Sieve of Eratosthenes | Time complexity is approximately |
First and Last Position of Element in Sorted Array - Binary Search - Leetcode 34 • NeetCode • 95,045 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