Count the Number of Ideal Arrays

Problem

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 10^9 + 7.

Examples

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 <= 10^4
• 1 <= maxValue <= 10^4

Solution

Method 1 - Maths + DP

The problem asks us to count distinct ideal arrays of length n. An array arr is ideal if:

1. Every arr[i] lies between 1 and maxValue.
2. Every element arr[i] is divisible by arr[i - 1] for indices i > 0.

To solve this:

1. We consider dynamic programming (DP) and precomputation using combinations to avoid redundant calculations.
2. The array's construction follows a tree-like structure where each node (representing a number) connects to its multiples.

Here are the steps:

• For each length 1 <= len <= n, calculate the number of arrays originating from each element in 1 to maxValue.
• Use a DP table dp[j][k]: dp[j][k] is the number of valid arrays of length j with last element k.
• Populate the DP table by considering that dp[j][k] depends on the values at the previous length (j - 1) that are divisors of k.
• Incorporate precomputed combinations for efficiency while managing results modulo 10^9 + 7.

Code

Java

class Solution {
    static final int mod = 1000000007;
    int[] factMemo = new int[100000];
    int[][] dp = new int[100000][15];

    long power(long a, long b, long m) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = (res * a) % m;
            a = (a * a) % m;
            b >>= 1;
        }
        return res;
    }

    long fact(int x) {
        if (x == 0) return 1;
        if (factMemo[x] != 0) return factMemo[x];
        factMemo[x] = (int)((1L * x * fact(x - 1)) % mod);
        return factMemo[x];
    }

    long modInv(int a, int b) {
        return fact(a) * power(fact(b), mod - 2, mod) % mod * power(fact(a - b), mod - 2, mod) % mod;
    }

    public int idealArrays(int n, int maxValue) {
        int m = Math.min(n, 14);
        for (int i = 1; i <= maxValue; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = 0;
        for (int i = 1; i <= maxValue; i++) {
            dp[i][1] = 1;
            for (int j = 2; i * j <= maxValue; j++)
                for (int k = 1; k < m; k++)
                    dp[i * j][k + 1] += dp[i][k];
        }
        long res = 0;
        for (int i = 1; i <= maxValue; i++)
            for (int j = 1; j <= m; j++)
                res = (res + modInv(n - 1, n - j) * dp[i][j]) % mod;
        return (int)res;
    }
}

Python

MOD = 1000000007

class Solution:
    def __init__(self):
        self.fact_memo = [0] * 100000
        self.dp = [[0] * 15 for _ in range(100000)]

    def power(self, a, b, m):
        res = 1
        while b > 0:
            if b & 1:
                res = (res * a) % m
            a = (a * a) % m
            b >>= 1
        return res

    def fact(self, x):
        if x == 0:
            return 1
        if self.fact_memo[x] != 0:
            return self.fact_memo[x]
        self.fact_memo[x] = (x * self.fact(x - 1)) % MOD
        return self.fact_memo[x]

    def mod_inv(self, a, b):
        return (self.fact(a) * self.power(self.fact(b), MOD - 2, MOD) % MOD * self.power(self.fact(a - b), MOD - 2, MOD)) % MOD

    def idealArrays(self, n, maxValue):
        m = min(n, 14)
        for i in range(1, maxValue + 1):
            for j in range(1, m + 1):
                self.dp[i][j] = 0
        for i in range(1, maxValue + 1):
            self.dp[i][1] = 1
            for j in range(2, maxValue // i + 1):
                for k in range(1, m):
                    self.dp[i * j][k + 1] += self.dp[i][k]
        res = 0
        for i in range(1, maxValue + 1):
            for j in range(1, m + 1):
                res = (res + self.mod_inv(n - 1, n - j) * self.dp[i][j]) % MOD
        return int(res)

Complexity

• ⏰ Time complexity: - O(n × maxValue × log(maxValue)): DP computation requires iterating over divisors, which takes logarithmic time.
• 🧺 Space complexity: O(n × maxValue) for The DP table size.