How hard is LeetCode 1735. Count Ways to Make Array With Product?

LeetCode 1735. Count Ways to Make Array With Product is rated Hard on LeetCode.

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

The Python solution on this page runs in O(K \times \log \log K + N + m \times \log K).

What is the space complexity of LeetCode 1735. Count Ways to Make Array With Product?

The Python solution on this page uses O(N) auxiliary space.

What topics does LeetCode 1735. Count Ways to Make Array With Product cover?

LeetCode 1735. Count Ways to Make Array With Product is tagged Array, Math, Dynamic Programming, Combinatorics and Number Theory on LeetCode.

Count Ways to Make Array With Product — LeetCode 1735 Python Solution

HardArrayMathDynamic ProgrammingCombinatoricsNumber Theory

Problem: #1735
Pattern: Dynamic Programming
Reading time: 6 min
Source: leetcode.com

The problem

You are given a 2D integer array, queries. For each queries[i], where queries[i] = [ni, ki], find the number of different ways you can place positive integers into an array of size ni such that the product of the integers is ki.

Example

Input: queries = [[2,6],[5,1],[73,660]]
Output: [4,1,50734910]
Explanation: Each query is independent.

Python solution

Python

N = 10020
MOD = 10**9 + 7
f = [1] * N
g = [1] * N
p = defaultdict(list)
for i in range(1, N):
    f[i] = f[i - 1] * i % MOD
    g[i] = pow(f[i], MOD - 2, MOD)
    x = i
    j = 2
    while j <= x // j:
        if x % j == 0:
            cnt = 0
            while x % j == 0:
                cnt += 1
                x //= j
            p[i].append(cnt)
        j += 1
    if x > 1:
        p[i].append(1)


def comb(n, k):
    return f[n] * g[k] * g[n - k] % MOD


class Solution:
    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
        ans = []
        for n, k in queries:
            t = 1
            for x in p[k]:
                t = t * comb(x + n - 1, n - 1) % MOD
            ans.append(t)
        return ans

Complexity

Measure	Complexity
Time	O(K \times \log \log K + N + m \times \log K)
Space	O(N) auxiliary

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1735. Count Ways to Make Array With Product is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1735. Count Ways to Make Array With Product?: LeetCode 1735. Count Ways to Make Array With Product is rated Hard on LeetCode.
What is the time complexity of LeetCode 1735. Count Ways to Make Array With Product?: The Python solution on this page runs in O(K \times \log \log K + N + m \times \log K).
What is the space complexity of LeetCode 1735. Count Ways to Make Array With Product?: The Python solution on this page uses O(N) auxiliary space.
What topics does LeetCode 1735. Count Ways to Make Array With Product cover?: LeetCode 1735. Count Ways to Make Array With Product is tagged Array, Math, Dynamic Programming, Combinatorics and Number Theory on LeetCode.