# Count all subsequences having product less than K

Given a non negative array, find the number of subsequences having product smaller than K.

Examples:

```Input : [1, 2, 3, 4]
k = 10
Output :11
The subsequences are {1}, {2}, {3}, {4},
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4},
{1, 2, 3}, {1, 2, 4}

Input  : [4, 8, 7, 2]
k = 50
Output : 9
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

This problem can be solved using dynamic programming where dp[i][j] = number of subsequences having product less than i using first j terms of the array. Which can be obtained by : number of subsequences using first j-1 terms + number of subsequences that can be formed using j-th term.

## C++

 `// CPP program to find number of subarrays having ` `// product less than k. ` `#include ` `using` `namespace` `std; ` ` `  `// Function to count numbers of such subsequences ` `// having product less than k. ` `int` `productSubSeqCount(vector<``int``> &arr, ``int` `k) ` `{ ` `    ``int` `n = arr.size(); ` `    ``int` `dp[k + 1][n + 1]; ` `    ``memset``(dp, 0, ``sizeof``(dp)); ` ` `  `    ``for` `(``int` `i = 1; i <= k; i++) { ` `        ``for` `(``int` `j = 1; j <= n; j++) { ` `    `  `            ``// number of subsequence using j-1 terms ` `            ``dp[i][j] = dp[i][j - 1]; ` `   `  `            ``// if arr[j-1] > i it will surely make product greater ` `            ``// thus it won't contribute then ` `            ``if` `(arr[j - 1] <= i && arr[j - 1] > 0) ` ` `  `                ``// number of subsequence using 1 to j-1 terms ` `                ``// and j-th term ` `                ``dp[i][j] += dp[i/arr[j-1]][j-1] + 1; ` `        ``} ` `    ``} ` `    ``return` `dp[k][n]; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``vector<``int``> A; ` `    ``A.push_back(1); ` `    ``A.push_back(2); ` `    ``A.push_back(3); ` `    ``A.push_back(4); ` `    ``int` `k = 10; ` `    ``cout << productSubSeqCount(A, k) << endl; ` `} `

## Java

 `// Java program to find number of subarrays  ` `// having product less than k. ` `import` `java.util.*; ` `class` `CountSubsequences ` `{ ` `    ``// Function to count numbers of such  ` `    ``// subsequences having product less than k. ` `    ``public` `static` `int` `productSubSeqCount(ArrayList arr, ` `                                                 ``int` `k) ` `    ``{ ` `        ``int` `n = arr.size(); ` `        ``int` `dp[][]=``new` `int``[k + ``1``][n + ``1``]; ` `         `  `        ``for` `(``int` `i = ``1``; i <= k; i++) { ` `            ``for` `(``int` `j = ``1``; j <= n; j++) { ` `         `  `                ``// number of subsequence using j-1 terms ` `                ``dp[i][j] = dp[i][j - ``1``]; ` `         `  `                ``// if arr[j-1] > i it will surely make  ` `                ``// product greater thus it won't contribute ` `                ``// then ` `                ``if` `(arr.get(j-``1``) <= i && arr.get(j-``1``) > ``0``) ` `     `  `                    ``// number of subsequence using 1 to j-1 ` `                    ``// terms and j-th term ` `                    ``dp[i][j] += dp[i/arr.get(j - ``1``)][j - ``1``] + ``1``; ` `            ``} ` `        ``} ` `        ``return` `dp[k][n]; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``ArrayList A = ``new` `ArrayList(); ` `        ``A.add(``1``); ` `        ``A.add(``2``); ` `        ``A.add(``3``); ` `        ``A.add(``4``); ` `        ``int` `k = ``10``; ` `        ``System.out.println(productSubSeqCount(A, k)); ` `    ``} ` `} ` ` `  `// This Code is contributed by Danish Kaleem `

/div>

## C#

 `// C# program to find number of subarrays  ` `// having product less than k.  ` `using` `System ; ` `using` `System.Collections ; ` ` `  `class` `CountSubsequences  ` `{  ` `    ``// Function to count numbers of such  ` `    ``// subsequences having product less than k.  ` `    ``public` `static` `int` `productSubSeqCount(ArrayList arr, ``int` `k)  ` `    ``{  ` `        ``int` `n = arr.Count ; ` `        ``int` `[,]dp = ``new` `int``[k + 1,n + 1];  ` `         `  `        ``for` `(``int` `i = 1; i <= k; i++) {  ` `            ``for` `(``int` `j = 1; j <= n; j++) {  ` `         `  `                ``// number of subsequence using j-1 terms  ` `                ``dp[i,j] = dp[i,j - 1];  ` `         `  `                ``// if arr[j-1] > i it will surely make  ` `                ``// product greater thus it won't contribute  ` `                ``// then  ` `                ``if` `(Convert.ToInt32(arr[j-1]) <= i && Convert.ToInt32(arr[j-1]) > 0)  ` `     `  `                    ``// number of subsequence using 1 to j-1  ` `                    ``// terms and j-th term  ` `                    ``dp[i,j] += dp[ i/Convert.ToInt32(arr[j - 1]),j - 1] + 1;  ` `            ``}  ` `        ``}  ` `        ``return` `dp[k,n];  ` `    ``}  ` `     `  `    ``// Driver code  ` `    ``public` `static` `void` `Main()  ` `    ``{  ` `        ``ArrayList A = ``new` `ArrayList();  ` `        ``A.Add(1);  ` `        ``A.Add(2);  ` `        ``A.Add(3);  ` `        ``A.Add(4);  ` `        ``int` `k = 10;  ` `        ``Console.WriteLine(productSubSeqCount(A, k));  ` `    ``}  ` `}  ` ` `  `// This Code is contributed Ryuga  `

## Python3

 `# Python3 program to find  ` `# number of subarrays having  ` `# product less than k.  ` `def` `productSubSeqCount(arr, k): ` `    ``n ``=` `len``(arr) ` `    ``dp ``=` `[[``0` `for` `i ``in` `range``(n ``+` `1``)] ` `             ``for` `j ``in` `range``(k ``+` `1``)] ` `    ``for` `i ``in` `range``(``1``, k ``+` `1``): ` `        ``for` `j ``in` `range``(``1``, n ``+` `1``): ` `             `  `            ``# number of subsequence ` `            ``# using j-1 terms  ` `            ``dp[i][j] ``=` `dp[i][j ``-` `1``] ` `             `  `            ``# if arr[j-1] > i it will  ` `            ``# surely make product greater ` `            ``# thus it won't contribute then  ` `            ``if` `arr[j ``-` `1``] <``=` `i ``and` `arr[j ``-` `1``] > ``0``: ` `                 `  `                ``# number of subsequence ` `                ``# using 1 to j-1 terms ` `                ``# and j-th term ` `                ``dp[i][j] ``+``=` `dp[i ``/``/` `arr[j ``-` `1``]][j ``-` `1``] ``+` `1` `    ``return` `dp[k][n] ` ` `  `# Driver code  ` `A ``=` `[``1``,``2``,``3``,``4``] ` `k ``=` `10` `print``(productSubSeqCount(A, k)) ` ` `  `# This code is contributed  ` `# by pk_tautolo `

Output:

```11
```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

code

load comments