2338. Count the Number of Ideal Arrays LeetCode Solution
In this guide, you will get 2338. Count the Number of Ideal Arrays LeetCode Solution with the best time and space complexity. The solution to Count the Number of Ideal Arrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count the Number of Ideal Arrays
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 from 1 to maxValue, for 0 <= i < n.
Every 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.
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 <= 104
1 <= maxValue <= 104
Complexity Analysis
Time Complexity: O(\texttt{maxValue})
Space Complexity: O(\texttt{maxValue})
2338. Count the Number of Ideal Arrays LeetCode Solution in C++
class Solution {
public:
int idealArrays(int n, int maxValue) {
// Since 2^14 > 10^4, the longest strictly increasing array is [1, 2, 4,
// ..., 2^13]
const int maxLength = min(14, n);
const vector<vector<int>> factors = getFactors(maxValue);
// dp[i][j] := the number of strictly increasing ideal arrays of length i
// ending in j
// dp[i][j] := sum(dp[i - 1][k]), where j % k == 0
// dp[i][0] := sum(dp[i][j]) where 1 <= j <= maxValue
vector<vector<long>> dp(maxLength + 1, vector<long>(maxValue + 1));
vector<vector<long>> mem(n, vector<long>(maxLength, -1));
long ans = 0;
for (int j = 1; j <= maxValue; ++j)
dp[1][j] = 1;
for (int i = 2; i <= maxLength; ++i)
for (int j = 1; j <= maxValue; ++j)
for (const int k : factors[j]) {
dp[i][j] += dp[i - 1][k];
dp[i][j] %= kMod;
}
for (int i = 1; i <= maxLength; ++i)
for (int j = 1; j <= maxValue; ++j) {
dp[i][0] += dp[i][j];
dp[i][0] %= kMod;
}
for (int i = 1; i <= maxLength; ++i) {
// nCk(n - 1, i - 1) := the number of ways to create an ideal array of
// length n from a strictly increasing array of length i
ans += dp[i][0] * nCk(n - 1, i - 1, mem);
ans %= kMod;
}
return ans;
}
private:
static constexpr int kMod = 1'000'000'007;
vector<vector<int>> getFactors(int maxValue) {
vector<vector<int>> factors(maxValue + 1);
for (int i = 1; i <= maxValue; ++i)
// Start from i * 2 because of strictly increasing.
for (int j = i * 2; j <= maxValue; j += i)
factors[j].push_back(i);
return factors;
}
long nCk(int n, int k, vector<vector<long>>& mem) {
if (k == 0)
return 1;
if (n == k)
return 1;
if (mem[n][k] != -1)
return mem[n][k];
return mem[n][k] = (nCk(n - 1, k, mem) + nCk(n - 1, k - 1, mem)) % kMod;
}
}; /* code provided by PROGIEZ */
2338. Count the Number of Ideal Arrays LeetCode Solution in Java
N/A // code provided by PROGIEZ
2338. Count the Number of Ideal Arrays LeetCode Solution in Python
