Count Ways to Make Array With Product - Practice Coding Problems

Count Ways to Make Array With Product - Problem

Array Math Dynamic Programming Combinatorics Number Theory Hard

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.

As the number of ways may be too large, the answer to the ith query is the number of ways modulo 10⁹ + 7.

Return an integer array answer where answer.length == queries.length, and answer[i] is the answer to the ith query.

Input & Output

Example 1 — Basic Query

$ Input: queries = [[2,6],[3,1]]

› Output: [4,1]

💡 Note: For [2,6]: arrays [1,6], [2,3], [3,2], [6,1] all have product 6, so 4 ways. For [3,1]: only [1,1,1] has product 1, so 1 way.

Example 2 — Single Element

$ Input: queries = [[1,10]]

› Output: [1]

💡 Note: Array of size 1 with product 10: only [10] works, so 1 way.

Example 3 — Larger Array

$ Input: queries = [[4,2]]

› Output: [4]

💡 Note: Arrays of size 4 with product 2: [2,1,1,1], [1,2,1,1], [1,1,2,1], [1,1,1,2], so 4 ways.

Constraints

1 ≤ queries.length ≤ 10⁴
1 ≤ ni ≤ 10⁴
1 ≤ ki ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Queries with array size n and target product k

Process

Use prime factorization and combinatorics

Output

Count of valid arrangements for each query

Key Takeaway

🎯 Key Insight: Transform multiplication constraints into combinatorial distribution of prime factors

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is to convert multiplication to addition using prime factorization. Each way to distribute prime factors across array positions corresponds to a valid arrangement. Best approach uses prime factorization + combinatorics with stars-and-bars formula. Time: O(√k + log k), Space: O(log k)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(k^n)	O(n)	Try all possible ways to fill array positions with positive integers
Prime Factorization + Combinatorics	O(√k + log k)	O(log k)	Use prime factorization and stars-and-bars to count arrangements

Brute Force Enumeration — Algorithm Steps

For each query, extract n and k
Generate all ways to partition k into n positive factors
Count valid arrangements using recursion

Visualization

Tap to expand

Step-by-Step Walkthrough

Input

Given n=2, k=6, find arrays of length 2 with product 6

Enumerate

Try all divisor combinations: [1,6], [2,3], [3,2], [6,1]

Count

Total valid ways = 4

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int countWays(int n, int k) {
    if (n == 1) return k >= 1 ? 1 : 0;
    if (k == 1) return n >= 1 ? 1 : 0;
    
    long long ways = 0;
    for (int i = 1; i <= k; i++) {
        if (k % i == 0) {
            ways = (ways + countWays(n - 1, k / i)) % MOD;
        }
    }
    return ways;
}

int* solution(int queries[][2], int queriesSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int n = queries[i][0];
        int k = queries[i][1];
        result[i] = countWays(n, k);
    }
    
    return result;
}

int main() {
    // Simple parsing for small test cases
    int queries[10][2];
    int queriesSize = 2;
    queries[0][0] = 2; queries[0][1] = 6;
    queries[1][0] = 3; queries[1][1] = 1;
    
    int returnSize;
    int* result = solution(queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

For each position, we try all divisors up to k, leading to exponential combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion depth is at most n levels deep

⚡ Linearithmic Space

15.6K Views

Medium Frequency

~35 min Avg. Time

420 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler