Cuente todas las subsecuencias que tengan un producto menor que K

Dada una array positiva, encuentre el número de subsecuencias que tienen un producto menor o igual que K.
Ejemplos: 

Entrada: [1, 2, 3, 4] 
        k = 10
Salida: 11 
Explicación : Las subsecuencias son {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4}

Entrada: [4, 8, 7, 2] 
         k = 50
Salida: 9

Este problema se puede resolver usando programación dinámica donde dp[i][j] = número de subsecuencias que tienen un producto menor que i usando los primeros j términos de la array. Que se puede obtener por: número de subsecuencias usando los primeros j-1 términos + número de subsecuencias que se pueden formar usando el j-ésimo término. 

A continuación se muestra la implementación del enfoque anterior:

// CPP program to find number of subarrays having
// product less than k.
#include <bits/stdc++.h>
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)
 
                // 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 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<Integer> 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<Integer> A = new ArrayList<Integer>();
        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

# 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

// 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

<script>
    // Javascript program to find number of subarrays
    // having product less than k.
     
    // Function to count numbers of such
    // subsequences having product less than k.
    function productSubSeqCount(arr, k)
    {
        let n = arr.length;
        let dp = new Array(k + 1);
        for (let i = 0; i < k + 1; i++)
        {
            dp[i] = new Array(n + 1);
            for (let j = 0; j < n + 1; j++)
            {
                dp[i][j] = 0;
            }
        }
           
        for (let i = 1; i <= k; i++) {
            for (let 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[parseInt(i/arr[j - 1], 10)][j - 1] + 1;
            }
        }
        return dp[k][n];
    }
     
    let A = [1, 2, 3, 4];
    let k = 10;
    document.write(productSubSeqCount(A, k));
     
    // This code is contributed by suresh07.
</script>

11

Complejidad de tiempo: O(K*N)
Espacio auxiliar: O(K*N)
Este artículo es una contribución de Raghav Sharma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.