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.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, 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^41 <= maxValue <= 10^4
Hints for Count the Number of Ideal Arrays
Hint 1
Group the arrays by their final value
x. The array is then a chain of divisors ending atx.Hint 2
Each prime of
xis distributed independently: its exponentehas to be split across thenpositions as a non-decreasing run.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
- 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 multiplyC(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, notn + e— the first position is where the chain starts. x = 1contributes 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 totalJava
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