304 North Cardinal St.
Dorchester Center, MA 02124

# Count the Number of Ideal Arrays LeetCode Solution

## Problem – Count the Number of Ideal Arrays LeetCode Solution

You are given two integers `n` and `maxValue`, which are used to describe an ideal array.

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.
``````

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 <= 104`
• `1 <= maxValue <= 104`

### Count the Number of Ideal Arrays LeetCode Solution in Java

``````import java.math.BigInteger;

class Solution {
public int idealArrays(int n, int maxValue) {
int m = 1000000007;
BigInteger res = BigInteger.ZERO;
long[][] dp = new long[maxValue + 1];
Map<Integer, List<Integer>> map = buildMap(maxValue);

// step 1: compute dp for the alternative problem (strictly increasing case)
for (int i = 1; i <= maxValue; i++) {
dp[i] = 1;
}
for (int i = 2; i <= n && i <= 14; i++) {
for (int j = 1; j <= maxValue; j++) {
for (int k : map.get(j)) {
dp[i][j] += dp[i - 1][k];
dp[i][j] %= m;
}
}
}
for (int i = 1; i <= n && i <= 14; i++) {
for (int j = 1; j <= maxValue; j++) {
dp[i] += dp[i][j];
dp[i] %= m; // dp[i] = number of ideal arrays (strictly increasing case) of length i
}
}

// step 2: use combinatorics to get the final answer for the actual problem from the alternative problem (strictly increasing case)
for (int i = 1; i <= n && i <= 14; i++) {
res = res.add(nCk(n - 1, i - 1).multiply(BigInteger.valueOf(dp[i])));
res = res.mod(BigInteger.valueOf(m));
}
return res.intValue();
}

// helper function to compute "n choose k"
private BigInteger nCk(int n, int k) {
BigInteger res = BigInteger.ONE;
for (int i = 1; i <=k; i++) {
res = res.multiply(BigInteger.valueOf(n - (i - 1))).divide(BigInteger.valueOf(i));
}
return res;
}

// helper funciton to build map {Integer -> {its divisors}}
private Map<Integer, List<Integer>> buildMap(int maxValue) {
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 1; i <= maxValue; i++) {
map.put(i, new ArrayList<>());
}
for (int i = 1; i <= maxValue; i++) {
int j = i * 2; // strictly increasing
while (j <= maxValue) {
j += i;
}
}
return map;
}
}
``````

### Count the Number of Ideal Arrays LeetCode Solution in Python

``````from math import sqrt

class Solution:
def primesUpTo(self, n):
primes = set(range(2, n + 1))
for i in range(2, n):
if i in primes:
it = i * 2
while it <= n:
if it in primes:
primes.remove(it)
it += i

return primes

def getPrimeFactors(self, n, primes):
ret = {}
sq = int(math.sqrt(n))

for p in primes:
if n in primes:
ret[n] = 1
break

while n % p == 0:
ret[p] = ret.get(p, 0) + 1
n //= p

if n <= 1:
break

return ret

def idealArrays(self, n: int, maxValue: int) -> int:
mod = 10**9 + 7
ret = 0
primes = self.primesUpTo(maxValue)

for num in range(1, maxValue + 1):
# find number of arrays that can end with num
# for each prime factor, we can add it at any index i that we want
pf = self.getPrimeFactors(num, primes)
cur = 1
for d in pf:
ct = pf[d]
v = n
# there are (n + 1) choose k ways to add k prime factors

cur = (cur * v) % mod

ret = (ret + cur) % mod

return ret
``````

### Count the Number of Ideal Arrays LeetCode Solution in C++

``````class Solution {
public:
int mod=1e9+7,mx;
long long dp,pr;
int n;
long long tot;
void get(int la,int cn){
tot[cn]++;
for(int p=2*la;p<=mx;p+=la)get(p,cn+1);
return;
}
int idealArrays(int nn, int mmx) {
n=nn;mx=mmx;
memset(dp,0,sizeof(dp));memset(pr,0,sizeof(pr));memset(tot,0,sizeof(tot));
for(int i=1;i<=10000;i++){
dp[i]=1;pr[i]=i;
}

for(int i=2;i<15;i++){
for(int j=i;j<=10000;j++){
dp[i][j]=pr[i-1][j-1];
pr[i][j]=dp[i][j]+pr[i][j-1];
dp[i][j]%=mod;
pr[i][j]%=mod;
}
}
long long ans=mx,x;
for(int i=1;i<=mx;i++){
get(i,1);
}
for(int i=2;i<15;i++){
x=tot[i]*dp[i][n];
x%=mod;
ans+=x;
ans%=mod;
}
return ans;
}
};
``````
##### Count the Number of Ideal Arrays LeetCode Solution Review:

In our experience, we suggest you solve this Count the Number of Ideal Arrays LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Count the Number of Ideal Arrays LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Count the Number of Ideal Arrays LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions