LeetCode 1735: Count Ways to Make Array With Product Solution

Master LeetCode problem 1735 (Count Ways to Make Array With Product), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1735. Count Ways to Make Array With Product

Hard

Array Math Dynamic Programming Combinatorics Number Theory

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will iterate through all possible factors of the given product k and for each factor that divides k, we will calculate the number of ways to form an array of size n with that factor as the maximum element. We will store these counts in a 2D array dp. The final answer for each query will be the sum of all possible ways to form the product k by considering all factors.

Initialize a 2D array dp of size n+1 x k+1 where dp[i][j] represents the number of ways to form an array of size i with product j.
For each query [n, k]:
- Iterate through all factors f of k.
- For each factor, calculate the number of ways to form an array of size n with f as the maximum element by considering all possible smaller factors.
- Update dp[n][k] accordingly.
Return the result for each query modulo 10^9 + 7.

Time Complexity: O(n * k * sqrt(k)) where n is the number of queries and k is the maximum product value in the queries. The inner loop runs for each factor of k.

Space Complexity: O(n * k) for the 2D array dp.

Solution Code

class Solution {
    public int[] waysToFillArray(int[][] queries) {
        int mod = 1000000007;
        int maxN = 10000;
        int[][] dp = new int[maxN + 1][maxN + 1];
        dp[0][1] = 1;

        for (int i = 1; i <= maxN; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i][j - 1]) % mod;
            }
        }

        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int n = queries[i][0];
            int k = queries[i][1];
            int ways = 1;

            for (int factor = 2; factor * factor <= k; factor++) {
                if (k % factor == 0) {
                    int count = 0;
                    while (k % factor == 0) {
                        count++;
                        k /= factor;
                    }
                    ways = (int) ((long) ways * dp[n + count - 1][count] % mod);
                }
            }

            if (k > 1) {
                ways = (int) ((long) ways * dp[n][1] % mod);
            }

            result[i] = ways;
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1735 (Count Ways to Make Array With Product)?

This page provides optimized solutions for LeetCode problem 1735 (Count Ways to Make Array With Product) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1735 (Count Ways to Make Array With Product)?

The time complexity for LeetCode 1735 (Count Ways to Make Array With Product) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1735 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1735 in Java, C++, or Python.

Back to LeetCode Solutions