Tutorialspoint.dev

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

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

/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

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter