Count the Number of Ideal Arrays — Hard Problem & Solution

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.

Difficulty: Hard
Topics: Math, Dynamic Programming, Number Theory, Combinatorics
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

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

Sieve the smallest prime factor up to maxValue.
Precompute the inverse factorials for exponents up to 13 — no exponent can exceed that below 10⁴.
For each x, factorize it and multiply C(n - 1 + e, e) over its prime exponents.
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue