Count the Number of Ideal Arrays

Hard
1097.

Count the Number of Ideal Arrays

Count the Number of Ideal Arrays is a hard coding problem on dynamic programming, math and number theory, asked in Amazon, Google and Meta interviews.

An array of length n is ideal when every entry lies in [1, maxValue] and each entry from the second onward is divisible by the one before it.

Return the number of ideal arrays, modulo 10⁹ + 7.

Example 1

Input
n = 2, maxValue = 5
Output
10
Explanation
`[1,1]`, `[1,2]`, `[1,3]`, `[1,4]`, `[1,5]`, `[2,2]`, `[2,4]`, `[3,3]`, `[4,4]`, `[5,5]`.

Example 2

Input
n = 5, maxValue = 3
Output
11
Explanation
The all-ones array, plus five placements each for a run of 2s and a run of 3s.

Example 3

Input
n = 3, maxValue = 1
Output
1

Constraints

  • 2 <= n <= 10^4
  • 1 <= maxValue <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} maxValue
 * @return {number}
 */
var idealArrays = function(n, maxValue) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count the Number of Ideal Arrays — Problem & Solution

Count the Number of Ideal Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Count the Number of Ideal Arrays is a hard coding problem on dynamic programming, math and number theory, asked in Amazon, Google and Meta interviews.

Problem statement

An array of length n is ideal when every entry lies in [1, maxValue] and each entry from the second onward is divisible by the one before it.

Return the number of ideal arrays, modulo 10⁹ + 7.

Example 1

Input: n = 2, maxValue = 5
Output: 10
Explanation: `[1,1]`, `[1,2]`, `[1,3]`, `[1,4]`, `[1,5]`, `[2,2]`, `[2,4]`, `[3,3]`, `[4,4]`, `[5,5]`.

Example 2

Input: n = 5, maxValue = 3
Output: 11
Explanation: The all-ones array, plus five placements each for a run of 2s and a run of 3s.

Example 3

Input: n = 3, maxValue = 1
Output: 1

Constraints

  • 2 <= n <= 10^4
  • 1 <= maxValue <= 10^4

Hints for Count the Number of Ideal Arrays

  1. Hint 1

    Group the arrays by their final value x. The array is then a chain of divisors ending at x.

  2. Hint 2

    Each prime of x is distributed independently: its exponent e has to be split across the n positions as a non-decreasing run.

  3. Hint 3

    That is C(n - 1 + e, e) ways per prime, and the primes multiply.

How to solve Count the Number of Ideal Arrays

Classify by the array's last value x. Building the array means deciding, for each prime power p^e dividing x, at which of the n positions each of the e factors of p is introduced — a multiset choice of e from n, which is C(n - 1 + e, e). The primes are independent, so the count for x is their product, and the answer sums over x.

Approach

  1. Sieve the smallest prime factor up to maxValue.
  2. Precompute the inverse factorials for exponents up to 13 — no exponent can exceed that below 10⁴.
  3. For each x, factorize it and multiply C(n - 1 + e, e) over its prime exponents.
  4. Sum the products modulo 10⁹ + 7.

Why it works

The primes factor apart because divisibility is decided prime by prime — a chain of divisors is just a non-decreasing exponent vector per prime, and those choices never interact. C(n - 1 + e, e) is the stars-and-bars count of ways to distribute e indistinguishable increments across n ordered positions, which is exactly where each factor of p enters the chain.

Complexity

  • Time — O(maxValue · log maxValue)
  • Space — O(maxValue)

Pitfalls

  • The binomial's top is n - 1 + e, not n + e — the first position is where the chain starts.
  • x = 1 contributes exactly 1 (the all-ones array) and has no primes to multiply.
  • The exponents are tiny, so the binomials need only a handful of inverse factorials rather than a full table up to n.

Reference solution

Python

def idealArrays(n: int, maxValue: int) -> int:
    MOD = 10**9 + 7
    MAXE = 14
    fact = [1] * (MAXE + 1)
    for i in range(1, MAXE + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact = [1] * (MAXE + 1)
    inv_fact[MAXE] = pow(fact[MAXE], MOD - 2, MOD)
    for i in range(MAXE, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % MOD

    def choose(top: int, e: int) -> int:
        num = 1
        for t in range(e):
            num = num * ((top + t) % MOD) % MOD
        return num * inv_fact[e] % MOD

    spf = [0] * (maxValue + 1)
    for p in range(2, maxValue + 1):
        if spf[p]:
            continue
        for q in range(p, maxValue + 1, p):
            if spf[q] == 0:
                spf[q] = p
    total = 0
    for x in range(1, maxValue + 1):
        ways = 1
        t = x
        while t > 1:
            p = spf[t]
            e = 0
            while t % p == 0:
                t //= p
                e += 1
            ways = ways * choose(n, e) % MOD
        total = (total + ways) % MOD
    return total

Java

public static int idealArrays(int n, int maxValue) {
    final long MOD = 1000000007L;
    final int MAXE = 14;
    long[] fact = new long[MAXE + 1];
    fact[0] = 1;
    for (int i = 1; i <= MAXE; i++) fact[i] = fact[i - 1] * i % MOD;
    long[] invFact = new long[MAXE + 1];
    long base = fact[MAXE], e = MOD - 2, cur = 1;
    while (e > 0) {
        if ((e & 1L) == 1L) cur = cur * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    invFact[MAXE] = cur;
    for (int i = MAXE; i >= 1; i--) invFact[i - 1] = invFact[i] * i % MOD;
    int[] spf = new int[maxValue + 1];
    for (int p = 2; p <= maxValue; p++) {
        if (spf[p] != 0) continue;
        for (int q = p; q <= maxValue; q += p) {
            if (spf[q] == 0) spf[q] = p;
        }
    }
    long total = 0;
    for (int x = 1; x <= maxValue; x++) {
        long ways = 1;
        int t = x;
        while (t > 1) {
            int p = spf[t];
            int exp = 0;
            while (t % p == 0) {
                t /= p;
                exp++;
            }
            long num = 1;
            for (int s = 0; s < exp; s++) num = num * ((n + s) % MOD) % MOD;
            ways = ways * (num * invFact[exp] % MOD) % MOD;
        }
        total = (total + ways) % MOD;
    }
    return (int) total;
}

C++

int idealArrays(int n, int maxValue) {
    const long long MOD = 1000000007LL;
    const int MAXE = 14;
    vector<long long> fact(MAXE + 1, 1), invFact(MAXE + 1, 1);
    for (int i = 1; i <= MAXE; i++) fact[i] = fact[i - 1] * i % MOD;
    long long base = fact[MAXE], e = MOD - 2, cur = 1;
    while (e > 0) {
        if (e & 1LL) cur = cur * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    invFact[MAXE] = cur;
    for (int i = MAXE; i >= 1; i--) invFact[i - 1] = invFact[i] * i % MOD;
    vector<int> spf(maxValue + 1, 0);
    for (int p = 2; p <= maxValue; p++) {
        if (spf[p] != 0) continue;
        for (int q = p; q <= maxValue; q += p) {
            if (spf[q] == 0) spf[q] = p;
        }
    }
    long long total = 0;
    for (int x = 1; x <= maxValue; x++) {
        long long ways = 1;
        int t = x;
        while (t > 1) {
            int p = spf[t];
            int exp = 0;
            while (t % p == 0) {
                t /= p;
                exp++;
            }
            long long num = 1;
            for (int s = 0; s < exp; s++) num = num * ((n + s) % MOD) % MOD;
            ways = ways * (num * invFact[exp] % MOD) % MOD;
        }
        total = (total + ways) % MOD;
    }
    return (int) total;
}

JavaScript

var idealArrays = function(n, maxValue) {
    var MOD = 1000000007, i;
    var mulmod = function(a, b) {
        var hi = Math.floor(a / 65536), lo = a % 65536;
        return ((hi * b % MOD) * 65536 + lo * b) % MOD;
    };
    var powmod = function(base, exp) {
        var result = 1, bb = base % MOD, e = exp;
        while (e > 0) {
            if (e % 2 === 1) result = mulmod(result, bb);
            bb = mulmod(bb, bb);
            e = Math.floor(e / 2);
        }
        return result;
    };
    var MAXE = 14;
    var fact = [1];
    for (i = 1; i <= MAXE; i++) fact.push(mulmod(fact[i - 1], i));
    var invFact = [];
    for (i = 0; i <= MAXE; i++) invFact.push(1);
    invFact[MAXE] = powmod(fact[MAXE], MOD - 2);
    for (i = MAXE; i >= 1; i--) invFact[i - 1] = mulmod(invFact[i], i);
    var choose = function(top, e) {
        var num = 1;
        for (var t = 0; t < e; t++) num = mulmod(num, (top + t) % MOD);
        return mulmod(num, invFact[e]);
    };
    var spf = [];
    for (i = 0; i <= maxValue; i++) spf.push(0);
    for (var p = 2; p <= maxValue; p++) {
        if (spf[p] !== 0) continue;
        for (var q = p; q <= maxValue; q += p) if (spf[q] === 0) spf[q] = p;
    }
    var total = 0;
    for (var x = 1; x <= maxValue; x++) {
        var ways = 1, t = x;
        while (t > 1) {
            var pf = spf[t];
            var e = 0;
            while (t % pf === 0) { t = t / pf; e++; }
            ways = mulmod(ways, choose(n, e));
        }
        total = (total + ways) % MOD;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming