Count Ways to Make Array With Product

Count Ways to Make Array With Product

What is this problem about?

The Count Ways to Make Array With Product interview question asks you to solve multiple queries. For each query [n, k], find the number of arrays of length n such that the product of all elements is k. The elements of the array must be positive integers. Since the count can be large, return it modulo $10^9 + 7$.

Why is this asked in interviews?

Amazon asks this Hard coding problem to test a candidate's knowledge of "Stars and Bars" combinatorics and prime factorization. It requires you to break down a product constraint into individual prime factor constraints. It evaluates your ability to use precomputed factorials and modular arithmetic to answer queries in O(log k) or O(number of factors).

Algorithmic pattern used

1. Prime Factorization: For a given $k$, find its prime factorization: $k = p_1^{a_1} imes p_2^{a_2} imes ...$.
2. Combinatorics (Stars and Bars): To distribute the product among $n$ slots, you must distribute each prime factor independently. For a prime factor $p_i$ with exponent $a_i$, the number of ways to distribute it into $n$ slots is the number of ways to choose $a_i$ items from $n$ categories with replacement: $\binom{a_i + n - 1}{n - 1}$.
3. Product Rule: The total ways for a query is the product of combinations for each prime factor: $\prod \binom{a_i + n - 1}{n - 1} \pmod{MOD}$.

Example explanation

Query: n = 2, k = 6

1. Prime factors of 6: $2^1 imes 3^1$.
2. Distribute factor 2: $\binom{1 + 2 - 1}{2 - 1} = \binom{2}{1} = 2$. (Ways: [2, 1], [1, 2]).
3. Distribute factor 3: $\binom{1 + 2 - 1}{2 - 1} = \binom{2}{1} = 2$. (Ways: [3, 1], [1, 3]).
4. Total ways: $2 imes 2 = 4$. The arrays are: [6, 1], [1, 6], [2, 3], [3, 2].

Common mistakes candidates make

• Factorizing inside queries: Not using a sieve to precompute primes, leading to TLE for many queries.
• Forgetting Stars and Bars: Trying to use DP for every query instead of the combinatorial formula.
• Product vs Sum: Confusing the "product is k" rule with "sum is k."

Interview preparation tip

Master the "Stars and Bars" formula. It's the go-to technique for "distributing $X$ identical items into $Y$ distinct bins" problems.