Leetcode Problem 1735. Count Ways to Make Array With Product

1735. Count Ways to Make Array With Product

Leetcode Solutions

Prime Factorization and Combinatorics

  1. Precompute the binomial coefficients (combinations) using Pascal's triangle and store them in a 2D array comb.
  2. Iterate over each query [n, k].
  3. Perform prime factorization of k and count the multiplicity of each prime factor.
  4. For each prime factor with its multiplicity r, calculate the number of ways to distribute r indistinguishable items into n distinguishable bins using the stars and bars method, which is comb[n - 1 + r][r].
  5. Multiply the results for each prime factor to get the total number of ways for the current query.
  6. If k is not 1 after prime factorization, it means k is a prime number itself, and there are n ways to place it in the array.
  7. Take the product modulo 10^9 + 7 and add it to the result array.
  8. Return the result array after processing all queries.
UML Thumbnail

Dynamic Programming with Prime Factorization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...