Count all subsequences 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
def productSubSeqCount ( arr , k ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE dp = [ [ 0 for i in range ( n + 1 ) ] for j in range ( k + 1 ) ] NEW_LINE for i in range ( 1 , k + 1 ) : NEW_LINE INDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i ] [ j - 1 ] NEW_LINE if arr [ j - 1 ] <= i and arr [ j - 1 ] > 0 : NEW_LINE INDENT dp [ i ] [ j ] += dp [ i // arr [ j - 1 ] ] [ j - 1 ] + 1 NEW_LINE DEDENT DEDENT DEDENT return dp [ k ] [ n ] NEW_LINE DEDENT A = [ 1 , 2 , 3 , 4 ] NEW_LINE k = 10 NEW_LINE print ( productSubSeqCount ( A , k ) ) NEW_LINE