CODEWITHSUNDEEP
c++arraysrecursiondynamic-programming
Anurag mishra
Anurag mishra

Reputation: 25

Count All Sub sequences having Product less than K

Given a non-negative array, find the number of subsequences having a product smaller than K.

Examples:

Input : [1, 2, 3, 4] k = 10 Output :11

Input : [4, 8, 7, 2] k = 50 Output : 9

So, We want to count the number of subsequences whose product is less than K.

There are sub-problems, and it can be solved using Dynamic Programming

However, I tried to write down the recursive code for better understanding.

Note: I am getting an answer as 6, which is wrong. Can someone help me, How to foresee the correct Logic?

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

vector<int> A{1, 2, 3, 4};

int countSubsequence(int i, int prod, int K)
{
    if(prod > 1 && prod <= K)
        return 1;
        
    if(i >= A.size() || prod > K)
        return 0;

    return countSubsequence(i + 1, prod, K) + countSubsequence(i + 1, prod*A[i], K);
}

int main() 
{
    int K = 10;
    cout << countSubsequence(0, 1, K);
    
    return 0;
}

Upvotes: 1

Views: 1519

Answers (1)

MikeCAT
MikeCAT

Reputation: 75062

The condition

    if(prod > 1 && prod <= K)
        return 1;

will have it return from the function (for example) when [1, 2] is selected from [1, 2, 3, 4] and prevent it from searching for [1, 2, 3].

Also:

  • The condition prod <= K is wrong becasue you want the product smaller than K, not K or smaller.
  • You cannot distinguish "nothing is multiplied" and "only the number 1 is multiplied" when you use 1 as the initial value.

Try this:

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

vector<int> A{1, 2, 3, 4};

int countSubsequence(int i, int prod, int K)
{
    if(i >= A.size() && 0 <= prod && prod < K)
        return 1;
        
    if(i >= A.size() || prod >= K)
        return 0;

    return countSubsequence(i + 1, prod, K) + countSubsequence(i + 1, prod < 0 ? A[i] : prod*A[i], K);
}

int main() 
{
    int K = 10;
    cout << countSubsequence(0, -1, K);
    
    return 0;
}

Upvotes: 2

Related Questions