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[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

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

Leave a Reply

Your email address will not be published.