Count all subsequences having product less than K | C # program to find number of subarrays having product less than k . ; Function to count numbers of such subsequences having product less than k . ; number of subsequence using j - 1 terms ; if arr [ j - 1 ] > i it will surely make product greater thus it won 't contribute  then ; number of subsequence using 1 to j - 1 terms and j - th term ; Driver code
using System ; using System . Collections ; class CountSubsequences { 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 ++ ) { dp [ i , j ] = dp [ i , j - 1 ] ; if ( Convert . ToInt32 ( arr [ j - 1 ] ) <= i && Convert . ToInt32 ( arr [ j - 1 ] ) > 0 ) dp [ i , j ] += dp [ i / Convert . ToInt32 ( arr [ j - 1 ] ) , j - 1 ] + 1 ; } } return dp [ k , n ] ; } 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 ) ) ; } }