Count sequences of positive integers having product X

0 0 7 minutes read

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 i^th term is generated by raising i^th 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 10⁹ + 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(2^N)
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:

$ways[i] \space *= \dbinom {P[j] + i - 1}{i - 1}$

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.

$ways[i] \space -= \dbinom{i}{j} * ways[j]$

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 X
void 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 Code
int main()
{
    vector<int> arr = { 1, 1 };
 
    // Function call
    countWays(arr);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
static int [][]bin = new int[3000][3000];
 
// Function to print the total number
// of possible sequences with
// product X
static 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 Code
public 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 approach
bin = [[0 for i in range(3000)] 
          for i in range(3000)]
 
# Function to print the total number
# of possible sequences with
# product X
def 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 Code
if __name__ == '__main__':
     
    arr = [ 1, 1 ]
 
    # Function call
    countWays(arr)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
static int [,]bin = new int[3000, 3000];
 
// Function to print the total number
// of possible sequences with
// product X
static 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 Code
public 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 X
function 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 Code
var arr = [ 1, 1 ];
// Function call
countWays(arr);
 
</script>

Output

Time Complexity: O(N²)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!