Count all subsequences having product less than K

The problem “Count all subsequences having product less than K” states that you are given an array of integers. Now find the number of subsequences that have a product less than a given input K.

Example

a[] = {1, 2, 3, 4, 5}
k = 8

Number of subsequences less than 8: 11

Explanation

There are 11 subsequences which have product less than given k(=8). The subsequences are shown in the image above.

Approach

The problem has provided us with a sequence of integers, and an integer K. then we are told to find the number of subsequences that have a product of less than K. So, whenever we deal with subsequences, subsets, or subarrays. A naive approach is always to generate these sequences and then check whether the generated sequence satisfies our conditions or not?

This naive solution will surely exceed our time limit. So to solve the problem under the given time constraint. We are required to use Dynamic Programming. So here we will traverse over the input array. During the traversal, we will be filling the DP table simultaneously. We have two states for this DP problem, first is the product until now and the second is the index for the input array. We start with the product and check if we can get the required result with the numbers/elements from the input array.

Our dp array cell dp[i][j] denotes the number of subsequences that have product less than i and are formed using the first j elements of the input. So for finding dp[i][j], we are dependent on dp[i/a[j]][j] and dp[i][j-1]. So if a[i] > i, taking this element into the subsequence will mean that a[i] itself is greater than K. Thus this element will not be considered. So that is how we count all subsequences having product less than K.

Code

C++ code to count all subsequences having product less than K

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a[] = {1, 2, 3, 4, 5};
    int n = (sizeof a)/(sizeof a[0]);
    int k = 8;
    int dp[k][n+1];
    memset(dp, 0, sizeof(dp));

    for (int i=1;i<k;i++){
        for (int j=1;j<=n;j++){
            dp[i][j] = dp[i][j-1];
            if (a[j-1] <= i && a[j-1] > 0)
                dp[i][j] += dp[i/a[j-1]][j-1] + 1;
        }
    }

    cout<<dp[k-1][n];
}

11

Java code to count all subsequences having product less than K

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int a[] = {1, 2, 3, 4, 5};
      int n = a.length;
      int k = 8;
      int dp[][] = new int[k][n+1];
      for(int i=0;i<k;i++)
      	for(int j=0;j<n+1;j++)
      		dp[i][j] = 0;

      for (int i=1;i<k;i++){
          for (int j=1;j<=n;j++){
              dp[i][j] = dp[i][j-1];
              if (a[j-1] <= i && a[j-1] > 0)
                  dp[i][j] += dp[i/a[j-1]][j-1] + 1;
          }
      }
    System.out.println(dp[k-1][n]);
  }
}

11

Complexity Analysis

Time Complexity

O(N*K), because there are two states one being the index for the input array and the other being the product of the subsequence limit. They have an upper bound N and K, thus the time complexity is polynomial.

Space Complexity

O(N*K), because we created a 2D DP table with N*K cells. Thus the space complexity is also polynomial.