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.
![ways[i] \space *= \dbinom {P[j] + i - 1}{i - 1}](https://geeksforgeeks.org/wp-content/uploads/2023/11/wardslaus_rubhabha_quicklatex.com-140da1dfcc17ef6f96f3793d5a5a5dc6_l3.png "Rendered by QuickLaTeX.com")
- 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]](https://geeksforgeeks.org/wp-content/uploads/2023/11/dominic_rubhabha_quicklatex.com-72555ee29e746889825d6f8196f1df27_l3.png "Rendered by QuickLaTeX.com")
- 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 approachvar 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> |
Output
3
Time Complexity: O(N2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
