Count Number of Subsequences

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
26 upvotes
Asked in companies
Goldman SachsHCL TechnologiesAmazon

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

Try to find all subsequences using recursion.

Approaches (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. 

 

  1. 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:

  1. 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.
  2. If ‘IDX' >= 'N’  return 0.
  3. 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).

Code Solution
(100% EXP penalty)
Count Number of Subsequences
Full screen
Console