Physical Address
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.
A 0-indexed integer array arr of length n is considered ideal if the following conditions hold:
- Every
arr[i]is a value from1tomaxValue, for0 <= i < n. - Every
arr[i]is divisible byarr[i - 1], for0 < 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 <= 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[15][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[1][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][0] += dp[i][j];
dp[i][0] %= m; // dp[i][0] = 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][0])));
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) {
map.get(j).add(i);
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
for add in range(1, ct):
v *= (n + add)
v //= (add + 1)
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[15][10001],pr[15][10001];
int n;
long long tot[15];
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[1][i]=1;pr[1][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
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 >>
