Count Sequences Of Positive Integers Having Product X

The idea is to make use of a combinatorics approach to find the contribution made by each element of the array in a total number of sequences.

1. The maximum number of positive integers in a sequence can be equal to the total sum of array elements, as explained below.
2. If given array is {1,1} then :
   • {1,1} =  2^1 * 3^1  =  6  so we can  have a maximum 2 prime whose product is 6.
3. Let's say the total sum of array elements is S.
4. We will make an array of integers say ANS[S+1], initialize to zero, which will store the contribution made by ith array element to a total number of sequences.
5. We will also make a 2-D array of integers say BCOFF[500][500], BCOFF will store permutations of binomial coefficients.
6. Then use dynamic programming to fill the slots in the possible sequences starting from index 1 to S.
7. For each j-th prime number having power as ARR[j], divide all the ARR[j] primes into each of the i slots.
8. Use the Combinatorics Approach to divide ARR[j] elements into i slots.
9. Store the value in array ARR such that ARR[i] is updated as follows:
   • ARR[i]= ARR[i] * (ARR[j]+i-1)C(i-1).
10. Here we are using nCr, which is the method of selection of ‘r’ objects from a set of ‘n’ objects where the order of selection does not matter.
11. We can find this value from BCOFF array, or we can say : ARR[i]= ARR[i] * BCOFF[ ARR[j]+i-1 ][ i-1].
12. However, ANS will also contain the sequences with one or more than 1 slot empty, hence subtract the exact contribution for all slots where the number of slots filled is less than i.
13. For each of the slots from j = 1 to i-1, select j slots from i and subtract its contribution and update ARR[i] as ARR[i] = ARR[i]-BCOFF[i][j].
14. Now the sum of ANS elements will be our answer.

Let’s understand with an example:

• Let’s take an example {1,0,1}:
• Then the value of X = 2^1*3^0*5^1 = 10 .
• Now as the sum of the array is 2 (S=2), there can be a maximum of 2 numbers in sequences whose product is 10.
• ANS[3]= {0,0,0}.
• We will run a loop for i = 1 to i = 3 and inside this loop, we will run a loop for j = 0 to j < 2 and :
  • ANS[i]=1 and then ANS[i] will be multiplied by (ARR[j]+i-1)C(i-1), here we are dividing ARR[j] + i - 1 into i - 1 slots.
  • But ARR[i] will also contain the sequences with one or more than 1 slot empty, so to get the exact contribution we will do:
    • ANS[i] = ANS[i]- ANS[i]*(iCj).
• After completion of the above step, ANS will be [0,1,2] which will add up to 3.
• So our answer will be 3.

O(N * S), where N is the size of ‘NUM’ array/list and ‘S’ is the sum of all the elements of the given array.

As we are running two nested loops where the outer loop runs for ‘S’ times and the inner loop runs for ‘N’ times.

O(S), where ‘S’ is the sum of all the elements of the ‘NUM’ array.

We are using ‘ANS’ array/list of size ‘S’ and ‘BCOFF’ array of constant size. Hence, the overall space complexity is O(S).