2338. Count the Number of Ideal Arrays

Description

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.

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

 

Solutions

Solution: Dynamic Programming + Combinatorics

• Time complexity: O(maxValuelogmaxValue)
• Space complexity: O(n+maxValuelogmaxValue)

 

JavaScript

/**
 * @param {number} n
 * @param {number} maxValue
 * @return {number}
 */
const idealArrays = function (n, maxValue) {
  const MODULO = BigInt(10 ** 9 + 7);
  const maxN = Math.min(n, 14); // 2 ** 14 > 10 ** 4
  const dp = Array.from({ length: maxN + 1 }, () => new Array(maxValue + 1).fill(0n));
  const factors = Array.from({ length: maxValue + 1 }, () => []);
  const comb = Array.from({ length: n }, () => new Array(maxN).fill(-1));
  let result = 0n;

  const nCk = (n, k) => {
    if (!k || n === k) return 1n;
    if (comb[n][k] !== -1) return comb[n][k];
    const count = nCk(n - 1, k) + nCk(n - 1, k - 1);

    comb[n][k] = count;

    return count;
  };

  for (let factor = 1; factor <= maxValue; factor++) {
    for (let value = factor * 2; value <= maxValue; value += factor) {
      factors[value].push(factor);
    }
  }

  for (let value = 1; value <= maxValue; value++) {
    dp[1][value] = 1n;
  }

  for (let len = 2; len <= maxN; len++) {
    for (let value = 1; value <= maxValue; value++) {
      for (const factor of factors[value]) {
        dp[len][value] = (dp[len][value] + dp[len - 1][factor]) % MODULO;
      }
    }
  }

  for (let len = 1; len <= maxN; len++) {
    for (let value = 1; value <= maxValue; value++) {
      dp[len][0] = (dp[len][0] + dp[len][value]) % MODULO;
    }
  }

  for (let len = 1; len <= maxN; len++) {
    result = (result + nCk(n - 1, len - 1) * dp[len][0]) % MODULO;
  }

  return Number(result);
};