Problem

Submissions

Hints & solutions

Discuss

Count Number of Subsequences

Moderate

0/80

Average time to solve is 15m

Contributed by

24 upvotes

Asked in companies

Problem statement

Given an array of non-negative integers ‘A’ and an integer ‘P’, find the total number of subsequences of ‘A’ such that the product of any subsequence should not be more than ‘P’.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Note

You need to print your answer modulo 10^9 + 7.

For Example

Let us take  A = [1,2,3] and P = 4. 
All the subsequences not having product more than ‘4’ are {1}, {2}, {3}, {1,2}, {1,3}. Therefore count is equal to ‘5’.

Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains two integers, ‘N’-number of elements in the array and ‘P’.

The second line of each test case contains ‘N’ space-separated integers that make up ‘A’.

Output Format

For each test case, Print an integer denoting the count of subsequences not having a product more than ‘P’.

Print the output of each test case in a separate line.

Note

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints

1 <= T <= 10
1 <= N <= 10^3
1 <= A[i] <= 10^3
1 <= P <= 10^3

Where A[i] is array element at index ‘i’,  ‘P’ is product value.
The Sum of 'N' over all test cases is <= 10 ^ 3.

Time Limit: 1 sec

Sample Input 1:

2
3 8
2 3 5  
4 10
15 20 30 25

Sample Output 1:

4
0

Explanation For Sample Input 1:

Test Case 1: The given array is [2,3,5]. 
All the possible subsequences of this array are {2}, {3}, {5}, {2,3}, {2,5}, {3,5}, {2,3,5}. But product of elements of subsequence {2,5}, {3,5}, {2,3,5} is more than p i.e 8. Therefore required count is 4.

Test Case 2: The given array is [15, 20. 30, 25] and p=10. 
As all the subsequences have product more than10’. So answer equals 0.

Sample Input 2

2
5 6
2 7 3 6 1
6 24
1 5 4 9 8 16

Sample Output 2

9
13

Explanation For Sample Input 2:

Test Case 1: The given array is [2, 7, 3, 6, 1]. 
The total number of subsequences having product less than 6 are 9.

Test Case 2: The given array is [1, 5, 4, 9, 8, 16] 
The total number of subsequences having product less than 24 are 13.

Hint 1

Hint 2

Try to find all subsequences using recursion.

Approaches (2)

Approach 1

Approach 2

Recursion

Approach: A simple idea to solve this problem is to find all the subsequences and then check the product of every subsequence. This can be done using recursion.

Let countSubsequenceHelper(A, P, PR ,IDX) be our recursive function.
- ‘IDX’ store the index of array element.
- ‘PR’ store the product of subsequence and take a variable ‘CNT’ (initialized to 0) to count the number of subsequences.
- We start from ‘IDX’ = 0 and ‘P’ = -1.
- For every element at index ‘IDX’ i.e. ‘A[IDX]’, there are two choices-either we include ‘A[IDX]’ in subsequence or not.
  - If ‘A[IDX]’ is included:
    - We call the function recursively for ‘IDX’ = ‘IDX + 1’ and ‘PR' = ‘A[i]’ (if current value of ‘PR’ = -1) or ‘PR’ = ‘PR * A[IDX]’ (if ‘PR' != -1) and add result to ’CNT’.
  - If ‘A[IDX]’ is not included:
    - We call the function recursively for ‘IDX’ = ‘IDX + 1’ and ‘PR’ and add the result to ‘CNT’.

Base Case:

If ‘IDX’ >= ‘N’ and 0 ≤ ‘PR’ ≤ ‘P’, it means we have traversed the complete array and the product of the subsequence is not more than ‘P’.Therefore we found a subsequence and return 1.
If ‘IDX' >= 'N’ return 0.
Return ‘CNT’.

Time Complexity

O(2^N), where N is the number of elements in the array.

The number of recursive calls will get doubled with the addition of one element. Therefore for ‘N’ elements, complexity is of order 2^N.

Space Complexity

O(N), where N is the number of elements in the array.

We are using recursive approach and thus, stack will be used of atmost size N. Therefore space complexity is O(N).

(100% EXP penalty)

Count Number of Subsequences

gatik

Interview problems

recursion+memoization approach

int getSolMem(int i, int mul, vector<int>& a, int n, int p, vector<vector<int>>& dp) {

if (mul > p) {

return 0;

}

if (i == n) {

return 1;

}

if (dp[i][mul] != -1) {

return dp[i][mul];

}

int include = getSolMem(i + 1, mul * a[i], a, n, p, dp);

int exclude = getSolMem(i + 1, mul, a, n, p, dp);

return dp[i][mul] = (include + exclude) % mod;

}

// Now applying the tabulation to above problem

int countSubsequences(vector<int>& a, int n, int p) {

// vector<vector<int>> dp(n, vector<int>(p + 1, -1));

// return (getSolMem(0, 1, a, n, p, dp) - 1 + mod) % mod;

return solveTab(1,a,n,p);

}

48 views

0 replies

0 upvotes

Aakrit Bhandari

Interview problems

Easy C++ SOLUTION || RECURSION

#include <bits/stdc++.h>

int mod = 1e9+7;

int getsol(int i,int mul,vector<int>&a,int n,int p)

{

if(mul>p)

{

return 0;

}

if(i==n)

{

if(mul<=p)

{

return 1;

}

return 0;

}

int take =0+getsol(i+1,mul*a[i],a,n,p);

int nottake = 0+getsol(i+1,mul,a,n,p);

return (take+nottake)%mod;

}

int countSubsequences(vector <int> & a, int n, int p) {

// Write your code here.

vector<int>res;

return getsol(0,1,a,n,p)-1;

}

159 views

0 replies

0 upvotes

Karan Lakhadive

Interview problems

Count Number of Subsequences | Memoization

#include <bits/stdc++.h>

int mod = 1e9+7;

int sol(vector<int>& arr, int ind, int product, int p, vector<vector<int>>& dp) {

// Base case

if(ind<0) {

return 0;

}

if(ind==0) {

if(product*arr[0]<=p) {

return 1;

}else {

return 0;

}

if(dp[ind][product]!=-1) return dp[ind][product];

int notTake = sol(arr, ind - 1, product, p, dp);

int take = 0;

if (product * arr[ind]<= p) {

take = 1+sol(arr, ind - 1, product * arr[ind], p, dp);

}

return dp[ind][product]=take + notTake;

}

int countSubsequences(vector<int>& arr, int n, int p) {

vector<vector<int>> dp(n, vector<int>(p+1, -1));

return sol(arr, n - 1, 1, p, dp);

}

236 views

0 replies

0 upvotes

kshitij kumar dubey

Interview problems

wrong answer on last test case can someone tell the error

#include <bits/stdc++.h> 
int mod = 1e9 + 7;
int P;
int dp[1001][1001][2];

int solve(int idx, int p, vector<int>&arr, bool take){
    if(idx==arr.size()){
        if(p<=P && take) return 1;
        return 0;
    }
    if(dp[idx][p][take]!=-1) return dp[idx][p][take];
    if(p>P) return 0;

    
    int ways = 0;
    if(p<=P && take) ways = 1;

    ways = (ways + solve(idx+1,p*arr[idx],arr,true)%mod)%mod;
    ways = (ways + solve(idx+1,p,arr,false)%mod)%mod;

    return dp[idx][p][take] = ways;
}

int countSubsequences(vector < int > & a, int n, int p) {
    // Write your code here.
    P= p;
    memset(dp,-1,sizeof(dp));
    return solve(0,1,a,0);
}

98 views

0 replies

0 upvotes

Tina Gupta

Interview problems

cpp solution

#include <bits/stdc++.h>

int f(int idx,vector < int > & a,vector<vector<int>>&dp,int p,int product){

if(idx<0){

return 0;

}

if(idx==0){

if(product*a[idx]<=p){

return 1;

}

else{

return 0;

}

if(dp[idx][product]!=-1){

return dp[idx][product];

}

int pick=0;

if(product*a[idx]<=p){

pick=1+f(idx-1,a,dp,p,product*a[idx]);

}

int notPick=f(idx-1,a,dp,p,product);

//dp[idx]=pick+notPick;

return dp[idx][product]=pick+notPick;

}

int countSubsequences(vector < int > & a, int n, int p) {

// Write your code here.

//vector<int>dp(n,-1);

vector<vector<int>>dp(n,vector<int>(p+1,-1));

return f(n-1,a,dp,p,1);

}

157 views

0 replies

1 upvote

shaik Shareef

Interview problems

c++ dp solution

#include <bits/stdc++.h>

int solve(vector<int> &v,int i,int n,int p1,int p,vector<vector<int>> &dp)

{

if(i==n || p1>p)

{

return 0;

}

if(dp[i][p1]!=-1)

{

return dp[i][p1];

}

int a=0,b=0;

if (p1 * v[i] <= p) {

a = 1 + solve(v, i + 1, n, p1 * v[i], p,dp);

}

b=solve(v,i+1,n,p1,p,dp);

return dp[i][p1]=a+b;

}

int countSubsequences(vector < int > & a, int n, int p) {

vector<vector<int>> dp(n+1,vector<int> (p+1,-1));

int an=solve(a,0,n,1,p,dp);

return an;

// Write your code here.

}

105 views

0 replies

0 upvotes

Deepali Jha

Interview problems

C++ Solution

    #include <bits/stdc++.h> 
    long long mod;
    long long rec(int ind,vector<int>&a,int n,int p, long long pro,
    vector<vector<long long>>&dp)
    {
        if (ind==n) return 1;
        if (dp[ind][pro]!=-1) return dp[ind][pro];
        long long pick=0;
        long long notPick=rec(ind+1,a,n,p,pro,dp);
        long long temp=pro*(long long)a[ind];
        long long p2=p;
        if (p<temp)
        {
            return dp[ind][pro]=notPick;
        }
        pick=rec(ind+1,a,n,p,temp,dp);
        return dp[ind][pro]=(pick+notPick)%mod;
    }
    int countSubsequences(vector < int > & a, int n, int p)
    {
        mod=1e9+7;
        vector<vector<long long>>dp(n,vector<long long>(p+1,-1));
        return rec(0,a,n,p,1,dp)-1;
    }

200 views

0 replies

0 upvotes

Sumit Singh

Interview problems

done by recursion

#include <bits/stdc++.h>

//vector<vector<int>>ans;

void solve(vector < int >a,vector<int>op,vector<vector<int>>&ans) {

// vector<vector<int>>ans;

if(a.size()==0){

//for()

ans.push_back(op);

return;

}

vector<int>op1=op;

vector<int>op2=op;

op2.push_back(a[0]);

a.erase(a.begin()+0);

solve(a,op1,ans);

solve(a,op2,ans);

return;

}

int countSubsequences(vector < int > & a, int n, int p) {

// Write your code here.

vector<int>op;

vector<vector<int>>ans;

solve(a,op,ans);

int count=0;

long long mod=1e9+7;

for(int i=0;i<ans.size();i++){

long long int prod=1;

for(int j=0;j<ans[i].size();j++){

prod=((prod%mod)*(ans[i][j]%mod))%mod;

// cout<<ans[i][j]<<" ";

}

// cout<<endl;

if(prod<=p){

count++;

}

//because it also count empty sabsequece so 1 has to be minus

return count-1;

}

139 views

0 replies

0 upvotes

Prakhar Singh

Interview problems

can you please explain how to correct the code.code is compiling suceesfully , but all test cases are failed

#include <bits/stdc++.h>

int printS(int index, int s, int p, vector<int>& a, int n) {

if(s>index) return 0;

if (index == n) {

if(s==p)return 1;

else

return 0;

}

// ds.push_back(arr[index]);

s += a[index];

int l=printS(index + 1, s, p, a, n);

// ds.pop_back();

s -= a[index];

int r= printS(index + 1, s, p, a, n);

return l+r % 1000000007;

}

int countSubsequences(vector < int > & a, int n, int p) {

// Write your code here.

return printS(0, 0, p, a, n);

}

69 views

0 replies

0 upvotes

Anshu

Interview problems

Simplest solution c++| DP + memorization |

#include <bits/stdc++.h>

int solve(vector < int > & a,int p,int index,int product,vector<vector<int>>&dp){

if(product>p)

return 0;

if(index==a.size())

return 1;

if(dp[index][product]!=-1)

return dp[index][product];

int count=0;

// Exclude

count+=solve(a,p,index+1,product,dp);

//Include

count+=solve(a,p,index+1,product*a[index],dp);

return dp[index][product]=count;

}

int countSubsequences(vector < int > & a, int n, int p) {

// Write your code here.

vector<vector<int>>dp(a.size()+1,vector<int>(p+1,-1));

return solve(a,p,0,1,dp) -1;

}

204 views

0 replies

0 upvotes

Console