Count Ways to Make Array With Product: Prime Factorization and Combinatorics

Given a list of queries where each query is a pair [n, k], count the number of ways to fill an array of size n with positive integers such that the product of all elements equals k. Return each answer modulo 10^9 + 7.

This is LeetCode 1735: Count Ways to Make Array With Product. A few examples:

• n = 2, k = 6 returns 4 (arrays: [1,6], [2,3], [3,2], [6,1])
• n = 5, k = 1 returns 1 (only [1,1,1,1,1])
• n = 3, k = 12 returns 18

At first glance you might think about brute-force enumeration of all arrays, but that blows up immediately. The trick is to never think about the arrays directly. Instead, think about how prime factors distribute across positions.

Why this problem matters

Number theory problems show up more often in interviews than you might expect, especially at companies that value mathematical reasoning. Problems like this one test whether you can decompose a complex counting problem into independent sub-problems using prime factorization.

The core technique here, stars and bars, is one of the most versatile tools in combinatorics. It appears whenever you need to count the number of ways to distribute identical items into distinct bins. Once you recognize the pattern, an entire family of counting problems becomes approachable: distributing resources, partitioning integers, and counting multisets.

Getting comfortable with modular arithmetic is also valuable. Many counting problems require working modulo a large prime, which means you need Fermat's little theorem (or extended GCD) for modular division. This is a building block that shows up in competitive programming and in interview problems that involve large combinatorial answers.

The key insight

The breakthrough is realizing that you do not need to enumerate arrays. Instead, factor k into its prime decomposition:

k = p1^e1 * p2^e2 * ... * pm^em

Each element of the array is a positive integer. The product of all n elements equals k. That means each prime factor pi must be distributed across the n array positions. The exponent of pi in the j-th array element tells you how many copies of pi that position "uses."

For a single prime pi with exponent ei, you need to split ei identical copies among n distinct slots. This is exactly the stars and bars formula:

C(ei + n - 1, n - 1)

Since different primes are independent (they share no common factors), you multiply the results across all primes:

answer = product of C(ei + n - 1, n - 1) for each prime pi

For modular division when computing combinations, precompute factorials and use Fermat's little theorem: the modular inverse of a modulo a prime p is a^(p-2) mod p.

The solution

def ways_to_fill_array(queries: list[list[int]]) -> list[int]:
    MOD = 10**9 + 7
    MAX = 10013 + 14

    fact = [1] * MAX
    for i in range(1, MAX):
        fact[i] = fact[i - 1] * i % MOD

    inv_fact = [1] * MAX
    inv_fact[MAX - 1] = pow(fact[MAX - 1], MOD - 2, MOD)
    for i in range(MAX - 2, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

    def comb(n, r):
        if r < 0 or r > n:
            return 0
        return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD

    result = []
    for n, k in queries:
        ways = 1
        d = 2
        while d * d <= k:
            if k % d == 0:
                exp = 0
                while k % d == 0:
                    exp += 1
                    k //= d
                ways = ways * comb(exp + n - 1, n - 1) % MOD
            d += 1
        if k > 1:
            ways = ways * comb(1 + n - 1, n - 1) % MOD
        result.append(ways)

    return result

The algorithm precomputes factorials and their modular inverses up front so that each combination C(n, r) can be evaluated in O(1). Then for each query, it factors k by trial division and multiplies the stars-and-bars counts.

Visual walkthrough

Complexity analysis

For each of the q queries, trial division takes O(sqrt(k)) to factor k. Each combination lookup is O(1) after precomputation. The precomputation itself is O(MAX) where MAX is around 10,027, covering the largest possible value of e + n - 1 (since k can be at most 10^4 and n can be at most 10^4).

The building blocks

1. Prime factorization

Factor k by trial division. Check each candidate divisor d from 2 up to sqrt(k). If d divides k, count how many times and divide it out. Any remainder greater than 1 is a prime factor with exponent 1.

def factorize(k):
    factors = {}
    d = 2
    while d * d <= k:
        while k % d == 0:
            factors[d] = factors.get(d, 0) + 1
            k //= d
        d += 1
    if k > 1:
        factors[k] = 1
    return factors
# factorize(12) -> {2: 2, 3: 1}

2. Stars and bars (combinatorics)

The number of ways to place e identical items into n distinct bins is C(e + n - 1, n - 1). Think of it as arranging e stars and n - 1 bars in a row. The bars partition the stars into n groups, one per bin.

def stars_and_bars(e, n, comb_fn):
    return comb_fn(e + n - 1, n - 1)
# e=2, n=3 -> C(4,2) = 6

The comb function uses precomputed factorials for O(1) evaluation:

def comb(n, r):
    if r < 0 or r > n:
        return 0
    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD

Edge cases

• k = 1: The only way to make a product of 1 with positive integers is for every element to be 1. There is exactly 1 valid array regardless of n.
• n = 1: The array has a single element, which must equal k itself. There is exactly 1 valid array.
• k is prime: The factorization is just k^1. Stars and bars gives C(1 + n - 1, n - 1) = C(n, n - 1) = n ways. That makes sense: pick which of the n positions holds k, and fill the rest with 1.
• Large k with many small prime factors: For example, k = 2^13 = 8192. The exponent is 13, and C(13 + n - 1, n - 1) can be large, but modular arithmetic handles it.

From understanding to recall

You have seen how prime factorization turns a seemingly complex array-filling problem into a clean multiplication of combinatorial terms. The two building blocks, trial division and stars-and-bars, are each simple on their own. The insight is connecting them.

Under interview pressure, you need this connection to surface immediately: "product constraint means prime factorization, distributing exponents means stars and bars." Spaced repetition is how you build that reflex. Solve this problem from scratch today, then again in a few days, then a week later. Each time you will reconstruct the factorization loop and the combination formula a little faster, until the pattern is second nature.

Related posts

• Count Primes - Prime sieve, foundational prime number computation
• Perfect Squares - Number decomposition into components
• Combination Sum IV - Counting ways to reach a target, combinatorial DP

These problems share the theme of decomposing a target into parts and counting the arrangements. Mastering the prime factorization and combinatorics patterns in this problem will make all of them feel more familiar.