4

Count Number of Subsequences

Difficulty: MEDIUM
Contributed By
Shrey Pansuria
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

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’.
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 <= 50
1 <= N <= 10^3
1 <= A[i] <= 10^3
1 <= P <= 10^8

Where A[i] is array element at index ‘i’,  ‘P’ is product value.

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.
Reset Code
Full screen
copy-code
Console