Given an array arr[] of size N, the task is to find the total number of sequences of positive integers possible (greater than 1) whose product is exactly X. The value of X is calculated as the product of the terms where ith term is generated by raising ith prime number to the power of arr[i].
X = 2 ^ arr[1] * 3 ^ arr[2] * 5 ^ arr[3] * 7 ^ arr[4] * 11 ^ arr[5] * … up to Nth term
Note: As the number of a total number of such sequences can be very large, print the answer modulo 109 + 7.
Examples:Â
Input: arr[] = {1, 1}Â
Output: 3Â
Explanation:Â
Here, X = 2^1 * 3^1 = 6Â
Possible positive sequences whose product is X: {2, 3}, {3, 2}, {6}Input: arr[] = {2}Â
Output: 2Â
Explanation:Â
Here, X = 2^2 = 4.Â
Possible positive sequences whose product is X: {2, 2} and {4}.
Naive Approach: The idea is to first calculate the value of X and then generate all possible sequences whose product is X using recursion.
Time Complexity: O(2N)Â
Auxiliary Space: O(1)
Efficient Approach: This problem can be solved using Dynamic Programming and Combinatorics Approach. Below are the steps:
- First, find the maximum number of positive elements that can appear in all of the possible sequences which will be the sum of given array arr[].
- Then use dynamic programming to fill the slots in the possible sequences starting index i from 1 to length of the sequence.Â
- For each j-th prime number having value as P[j], divide all the P[j] primes into each of the i slots.
- Use the Combinatorics Approach to divide P[j] elements into i slots. Store the value in array ways[] such that ways[i] is updated as follows:
ÂNumber of ways to divide N identical elements into K slots = (N + K – 1)C(K – 1)Â
This approach is also known as Stars and Bars approach formally in Combinatorics. Â
- For each of the j primes, multiply the values as depicted by the multiplication.
- However, ways[] will also contain the sequences with one or more than 1 slot empty, hence subtract the exact contribution for all slots where number of slots filled is less than i.
- For each of the slots from j = 1 to i – 1, select j slots from i and subtract its contribution.
- Finally, add all the values of the array ways[] to get the total result.Â
Â
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;Â
int bin[3000][3000];Â
// Function to print the total number// of possible sequences with// product Xvoid countWays(const vector<int>& arr){Â Â Â Â int mod = 1e9 + 7;Â Â Â Â bin[0][0] = 1;Â
    // Precomputation of    // binomial coefficients    for (int i = 1; i < 3000; i++) {        bin[i][0] = 1;        for (int j = 1; j <= i; j++) {            bin[i][j] = (bin[i - 1][j]                         + bin[i - 1][j - 1])                        % mod;        }    }Â
    // Max length of a subsequence    int n = 0;    for (auto x : arr)        n += x;Â
    // Ways dp array    vector<int> ways(n + 1);Â
    for (int i = 1; i <= n; i++) {        ways[i] = 1;Â
        // Fill i slots using all        // the primes        for (int j = 0;             j < (int)arr.size(); j++) {            ways[i] = (ways[i]                       * bin[arr[j] + i - 1]                            [i - 1])                      % mod;        }Â
        // Subtract ways for all        // slots that exactly        // fill less than i slots        for (int j = 1; j < i; j++) {            ways[i] = ((ways[i]                        - bin[i][j] * ways[j])                           % mod                       + mod)                      % mod;        }    }Â
    // Total possible sequences    int ans = 0;    for (auto x : ways)        ans = (ans + x) % mod;Â
    // Print the resultant count    cout << ans << endl;}Â
// Driver Codeint main(){Â Â Â Â vector<int> arr = { 1, 1 };Â
    // Function call    countWays(arr);Â
    return 0;} |
Java
// Java program for the above approachimport java.util.*;Â
class GFG{Â
static int [][]bin = new int[3000][3000];Â
// Function to print the total number// of possible sequences with// product Xstatic void countWays(int[] arr){Â Â Â Â int mod = (int)1e9 + 7;Â Â Â Â bin[0][0] = 1;Â
    // Precomputation of    // binomial coefficients    for(int i = 1; i < 3000; i++)     {        bin[i][0] = 1;        for(int j = 1; j <= i; j++)         {            bin[i][j] = (bin[i - 1][j] +                          bin[i - 1][j - 1]) % mod;        }    }Â
    // Max length of a subsequence    int n = 0;    for(int x : arr)        n += x;Â
    // Ways dp array    int[] ways = new int[n + 1];Â
    for(int i = 1; i <= n; i++)    {        ways[i] = 1;Â
        // Fill i slots using all        // the primes        for(int j = 0; j < arr.length; j++)         {            ways[i] = (ways[i] *                     bin[arr[j] + i - 1][i - 1]) % mod;        }Â
        // Subtract ways for all        // slots that exactly        // fill less than i slots        for(int j = 1; j < i; j++)        {            ways[i] = ((ways[i] - bin[i][j] *                        ways[j]) % mod + mod) % mod;        }    }Â
    // Total possible sequences    int ans = 0;    for(int x : ways)        ans = (ans + x) % mod;Â
    // Print the resultant count    System.out.print(ans + "\n");}Â
// Driver Codepublic static void main(String[] args){Â Â Â Â int[] arr = { 1, 1 };Â
    // Function call    countWays(arr);}}Â
// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approachbin = [[0 for i in range(3000)] Â Â Â Â Â Â Â Â Â Â for i in range(3000)]Â
# Function to print the total number# of possible sequences with# product Xdef countWays(arr):Â Â Â Â Â Â Â Â Â mod = 10**9 + 7Â Â Â Â bin[0][0] = 1Â
    # Precomputation of    # binomial coefficients    for i in range(1, 3000):        bin[i][0] = 1                 for j in range(1, i + 1):            bin[i][j] = (bin[i - 1][j] +                         bin[i - 1][j - 1]) % modÂ
    # Max length of a subsequence    n = 0         for x in arr:        n += xÂ
    # Ways dp array    ways = [0] * (n + 1)Â
    for i in range(1, n + 1):        ways[i] = 1Â
        # Fill i slots using all        # the primes        for j in range(len(arr)):            ways[i] = (ways[i] *                    bin[arr[j] + i - 1][i - 1]) % modÂ
        # Subtract ways for all        # slots that exactly        # fill less than i slots        for j in range(1, i):            ways[i] = ((ways[i] - bin[i][j] *                        ways[j]) % mod + mod) % modÂ
    # Total possible sequences    ans = 0         for x in ways:        ans = (ans + x) % modÂ
    # Print the resultant count    print(ans)Â
# Driver Codeif __name__ == '__main__':Â Â Â Â Â Â Â Â Â arr = [ 1, 1 ]Â
    # Function call    countWays(arr)Â
# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;Â
class GFG{Â
static int [,]bin = new int[3000, 3000];Â
// Function to print the total number// of possible sequences with// product Xstatic void countWays(int[] arr){Â Â Â Â int mod = (int)1e9 + 7;Â Â Â Â bin[0, 0] = 1;Â
    // Precomputation of    // binomial coefficients    for(int i = 1; i < 3000; i++)     {        bin[i, 0] = 1;        for(int j = 1; j <= i; j++)         {            bin[i, j] = (bin[i - 1, j] +                          bin[i - 1, j - 1]) % mod;        }    }Â
    // Max length of a subsequence    int n = 0;    foreach(int x in arr)        n += x;Â
    // Ways dp array    int[] ways = new int[n + 1];Â
    for(int i = 1; i <= n; i++)    {        ways[i] = 1;Â
        // Fill i slots using all        // the primes        for(int j = 0; j < arr.Length; j++)         {            ways[i] = (ways[i] *                     bin[arr[j] + i - 1, i - 1]) % mod;        }Â
        // Subtract ways for all        // slots that exactly        // fill less than i slots        for(int j = 1; j < i; j++)        {            ways[i] = ((ways[i] - bin[i, j] *                        ways[j]) % mod + mod) % mod;        }    }Â
    // Total possible sequences    int ans = 0;    foreach(int x in ways)        ans = (ans + x) % mod;Â
    // Print the resultant count    Console.Write(ans + "\n");}Â
// Driver Codepublic static void Main(String[] args){Â Â Â Â int[] arr = { 1, 1 };Â
    // Function call    countWays(arr);}}Â
// This code is contributed by Amit Katiyar |
Javascript
<script>Â
// Javascript program for the above approachÂ
var bin = Array.from(Array(3000), ()=> Array(3000).fill(0));Â
// Function to print the total number// of possible sequences with// product Xfunction countWays(arr){Â Â Â Â var mod = 1000000007;Â Â Â Â bin[0][0] = 1;Â
    // Precomputation of    // binomial coefficients    for (var i = 1; i < 3000; i++) {        bin[i][0] = 1;        for (var j = 1; j <= i; j++) {            bin[i][j] = (bin[i - 1][j]                         + bin[i - 1][j - 1])                        % mod;        }    }Â
    // Max length of a subsequence    var n = 0;    for (var x =0; x<arr.length; x++)        n += arr[x];Â
    // Ways dp array    var ways = Array(n + 1).fill(0);Â
    for (var i = 1; i <= n; i++) {        ways[i] = 1;Â
        // Fill i slots using all        // the primes        for (var j = 0;             j <arr.length; j++) {            ways[i] = (ways[i]                       * bin[arr[j] + i - 1]                            [i - 1])                      % mod;        }Â
        // Subtract ways for all        // slots that exactly        // fill less than i slots        for (var j = 1; j < i; j++) {            ways[i] = ((ways[i]                        - bin[i][j] * ways[j])                           % mod                       + mod)                      % mod;        }    }Â
    // Total possible sequences    var ans = 0;    for (var i = 1; i <= n; i++)        ans = (ans + ways[i]) % mod;Â
    // Print the resultant count    document.write( ans );}Â
// Driver Codevar arr = [ 1, 1 ];// Function callcountWays(arr);Â
</script> |
3
Time Complexity: O(N2)Â
Auxiliary Space: O(N)
Â
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

![Rendered by QuickLaTeX.com ways[i] \space *= \dbinom {P[j] + i - 1}{i - 1}](https://cdn.geeksforgeeks.org/static/gallery/images/logo.png)
… [Trackback]
[…] Here you will find 61289 additional Information on that Topic: geeksforgeeks.org/count-sequences-of-positive-integers-having-product-x/ […]
… [Trackback]
[…] Read More here to that Topic: geeksforgeeks.org/count-sequences-of-positive-integers-having-product-x/ […]
… [Trackback]
[…] Read More on on that Topic: geeksforgeeks.org/count-sequences-of-positive-integers-having-product-x/ […]
… [Trackback]
[…] Find More on that Topic: geeksforgeeks.org/count-sequences-of-positive-integers-having-product-x/ […]