LeetCode 2338 - Count the Number of Ideal Arrays

LeetCode Problem 2338

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming, Combinatorics, Number Theory

Solution

Problem Understanding

The problem asks us to count how many arrays of length n satisfy a divisibility condition while keeping every value within the range [1, maxValue].

An array arr is considered ideal if:

1. Every element is between 1 and maxValue.
2. For every adjacent pair, the later element is divisible by the earlier one.

Formally, for every i > 0:

$$arr[i] \bmod arr[i - 1] = 0$$

This means the sequence can only stay the same or grow through multiplication by integers. For example:

• [1, 2, 4, 8] is valid because each number divides the next.
• [2, 6, 12] is valid because 6 % 2 == 0 and 12 % 6 == 0.
• [2, 3] is invalid because 3 % 2 != 0.

The goal is to count all distinct valid arrays of length n.

The constraints are important:

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

A brute force search over all possible arrays would require checking up to:

$$(maxValue)^n$$

which is astronomically large. Even for small values, exhaustive generation is impossible.

The key observation is that divisibility chains have strong mathematical structure. Instead of generating arrays directly, we can analyze how values evolve through prime factorization and combinatorics.

Some important edge cases include:

• maxValue = 1, where the only possible array is [1,1,...,1].
• Large n with small maxValue, where combinatorial counts become very large.
• Numbers with many prime factors, such as 840, which can generate many divisor chains.
• Arrays where all elements are equal, which are always valid because every number divides itself.

The problem guarantees valid positive integers, so we never need to handle zero or negative numbers.

Approaches

Brute Force Approach

The most direct approach is to generate every possible array of length n where each value lies between 1 and maxValue, then check whether the divisibility condition holds for every adjacent pair.

For each position, there are maxValue choices, so the total number of arrays is:

$$(maxValue)^n$$

For every generated array, we would verify:

$$arr[i] % arr[i-1] == 0$$

for all indices.

This approach is correct because it explicitly checks every possible candidate and counts only valid arrays.

However, it is completely infeasible. Even with n = 10 and maxValue = 10, there are already:

$$10^{10}$$

arrays to inspect.

The constraints are much larger, so brute force cannot work.

Key Insight

The divisibility condition creates multiplicative chains.

Suppose an ideal array ends with value x. If we write the prime factorization of x:

$$x = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$$

then moving through the array corresponds to gradually accumulating these prime exponents.

For example:

$$12 = 2^2 \times 3^1$$

To build a divisibility chain ending at 12, we need to distribute:

• two copies of prime 2
• one copy of prime 3

across the n positions in nondecreasing fashion.

This becomes a classic stars and bars combinatorics problem.

For an exponent a, the number of ways to distribute it across n positions is:

$$\binom{n-1+a}{a}$$

Since prime factors are independent, we multiply these counts together.

Thus, for each value x:

1. Factorize x
2. Compute combinations for each exponent
3. Multiply them together
4. Sum over all x

This transforms the problem from exponential search into manageable combinatorics plus number theory.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(maxValue^n × n)	O(n)	Generates all arrays explicitly
Optimal	O(maxValue × log(maxValue) + maxValue × log(maxValue))	O(maxValue + n)	Uses prime factorization and combinatorics

Algorithm Walkthrough

Step 1: Precompute Combination Values

We repeatedly need values of the form:

$$\binom{n-1+a}{a}$$

where a is a prime exponent.

Since maxValue <= 10^4, the maximum exponent is small, roughly 13 because:

$$2^{13} = 8192$$

We precompute Pascal's Triangle up to:

$$n + 14$$

This allows constant time combination lookup.

Step 2: Precompute Smallest Prime Factors

To factorize numbers efficiently, we build a sieve storing the smallest prime factor for every integer up to maxValue.

For example:

• spf[12] = 2
• spf[15] = 3

This allows fast factorization in logarithmic time.

Step 3: Iterate Through Every Ending Value

For every integer x from 1 to maxValue, we count how many ideal arrays can end with x.

We factorize x.

Example:

$$x = 72 = 2^3 \times 3^2$$

So the exponents are:

• 3
• 2

Step 4: Count Ways for Each Prime Exponent

For each exponent e, we compute:

$$\binom{n-1+e}{e}$$

This counts how many ways the exponent can increase across the array positions.

For exponent 3:

$$\binom{n+2}{3}$$

For exponent 2:

$$\binom{n+1}{2}$$

Step 5: Multiply Independent Contributions

Prime factors are independent.

So the total number of ideal arrays ending in x is:

$$\prod \binom{n-1+e_i}{e_i}$$

Step 6: Sum Over All Possible End Values

Add the contribution of every value from 1 to maxValue.

Return the result modulo:

$$10^9 + 7$$

Why it works

Every ideal array corresponds to a nondecreasing assignment of prime exponents across positions.

For a prime exponent e, we need to distribute e increments among n positions. The stars and bars theorem gives exactly:

$$\binom{n-1+e}{e}$$

ways to do this.

Since different primes evolve independently, multiplying the counts gives the exact number of valid arrays ending at a specific value. Summing over all ending values counts every ideal array exactly once.

Python Solution

class Solution:
    def idealArrays(self, n: int, maxValue: int) -> int:
        MOD = 10**9 + 7

        max_exp = 14

        # Precompute combinations using Pascal triangle
        size = n + max_exp + 1
        comb = [[0] * (max_exp + 1) for _ in range(size)]

        for i in range(size):
            comb[i][0] = 1
            for j in range(1, min(i, max_exp) + 1):
                comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD

        # Smallest prime factor sieve
        spf = list(range(maxValue + 1))

        for i in range(2, int(maxValue ** 0.5) + 1):
            if spf[i] == i:
                for j in range(i * i, maxValue + 1, i):
                    if spf[j] == j:
                        spf[j] = i

        answer = 0

        for value in range(1, maxValue + 1):
            ways = 1
            x = value

            while x > 1:
                prime = spf[x]
                exponent = 0

                while x % prime == 0:
                    x //= prime
                    exponent += 1

                ways = (
                    ways * comb[n - 1 + exponent][exponent]
                ) % MOD

            answer = (answer + ways) % MOD

        return answer

The implementation begins by precomputing combinations using Pascal's Triangle. We only need small exponents, so the combination table remains compact.

Next, the smallest prime factor sieve enables efficient factorization of every value from 1 to maxValue.

For each value, the code extracts prime exponents one by one. Every exponent contributes a combinatorial count representing how many ways that exponent can be distributed through the array positions.

The counts for different primes are multiplied together because their exponent progressions are independent.

Finally, all valid ending values are summed to obtain the total number of ideal arrays.

Go Solution

func idealArrays(n int, maxValue int) int {
	const MOD int = 1e9 + 7

	maxExp := 14
	size := n + maxExp + 1

	// Combination table
	comb := make([][]int, size)
	for i := range comb {
		comb[i] = make([]int, maxExp+1)
		comb[i][0] = 1

		for j := 1; j <= min(i, maxExp); j++ {
			comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD
		}
	}

	// Smallest prime factor sieve
	spf := make([]int, maxValue+1)
	for i := 0; i <= maxValue; i++ {
		spf[i] = i
	}

	for i := 2; i*i <= maxValue; i++ {
		if spf[i] == i {
			for j := i * i; j <= maxValue; j += i {
				if spf[j] == j {
					spf[j] = i
				}
			}
		}
	}

	answer := 0

	for value := 1; value <= maxValue; value++ {
		ways := 1
		x := value

		for x > 1 {
			prime := spf[x]
			exponent := 0

			for x%prime == 0 {
				x /= prime
				exponent++
			}

			ways = (ways * comb[n-1+exponent][exponent]) % MOD
		}

		answer = (answer + ways) % MOD
	}

	return answer
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the same algorithmic structure as the Python version.

One important difference is explicit integer handling. Since multiplication can overflow standard 32-bit integers on some systems, Go's int type is relied upon together with modular reduction after every multiplication.

Slices are used instead of dynamic Python lists, and helper functions are needed because Go does not provide built-in utilities like min.

Worked Examples

Example 1

Input:

n = 2
maxValue = 5

We evaluate every ending value.

Value	Prime Factorization	Formula	Ways
1	none	1	1
2	2¹	C(2,1)	2
3	3¹	C(2,1)	2
4	2²	C(3,2)	3
5	5¹	C(2,1)	2

Now sum:

$$1 + 2 + 2 + 3 + 2 = 10$$

Output:

10

Example 2

Input:

n = 5
maxValue = 3

Evaluate values from 1 to 3.

Value	Prime Factors	Formula	Ways
1	none	1	1
2	2¹	C(5,1)	5
3	3¹	C(5,1)	5

Total:

$$1 + 5 + 5 = 11$$

Output:

11

Complexity Analysis

Measure	Complexity	Explanation
Time	O(maxValue × log(maxValue))	Each number is factorized efficiently using the sieve
Space	O(n + maxValue)	Combination table and SPF array dominate memory usage

The sieve construction requires near linear time. Each value is factorized in logarithmic time because repeated division quickly reduces the number. Since prime exponents remain small, the combinatorial work is constant per factor.

Test Cases

sol = Solution()

assert sol.idealArrays(2, 5) == 10  # provided example 1
assert sol.idealArrays(5, 3) == 11  # provided example 2

assert sol.idealArrays(1, 1) == 1  # smallest possible input
assert sol.idealArrays(1, 10) == 10  # every single element array is valid

assert sol.idealArrays(2, 1) == 1  # only [1,1]
assert sol.idealArrays(3, 1) == 1  # all ones

assert sol.idealArrays(2, 2) == 3  # [1,1], [1,2], [2,2]

assert sol.idealArrays(3, 2) == 4  # simple divisibility growth

assert sol.idealArrays(4, 3) == 9  # checks combinatorics with small primes

assert sol.idealArrays(10000, 1) == 1  # very large n, only one array

# stress style cases
assert isinstance(sol.idealArrays(10000, 10000), int)  # large constraints

Test	Why
n=2, maxValue=5	Validates provided example
n=5, maxValue=3	Validates repeated prime distribution
n=1, maxValue=1	Smallest boundary
n=1, maxValue=10	Every value independently valid
n=2, maxValue=1	Only one possible array
n=3, maxValue=1	All elements fixed to one
n=2, maxValue=2	Simple divisibility relationships
n=3, maxValue=2	Small chain counting
n=4, maxValue=3	Multiple prime handling
n=10000, maxValue=10000	Maximum constraint stress test

Edge Cases

One important edge case occurs when maxValue = 1. In this situation, the only allowed number is 1, and every array must therefore be:

$$[1,1,\dots,1]$$

A naive implementation might accidentally overcount or mishandle empty prime factorizations. This implementation correctly handles it because the factorization loop never executes for 1, leaving the contribution as exactly 1.

Another critical edge case is when n = 1. With only one position, the divisibility condition becomes irrelevant because there are no adjacent pairs to check. Every number from 1 to maxValue forms a valid array. The combinatorial formulas naturally produce this result because every exponent distribution has exactly one arrangement in a single slot.

Numbers with repeated prime powers are another potential source of bugs. Consider:

$$64 = 2^6$$

The exponent 6 must be distributed correctly across positions. Incorrect implementations may treat repeated factors independently rather than grouping them into one exponent count. This solution explicitly counts the full exponent before computing:

$$\binom{n-1+6}{6}$$

which correctly represents all valid exponent progressions.

A final subtle edge case involves very large outputs. The number of ideal arrays grows rapidly, especially for large n. Without modular arithmetic after every multiplication and addition, integer overflow would occur. Both implementations apply modulo 10^9 + 7 consistently throughout all computations.