'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Topics

Count Number of Subsequences

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
21 upvotes
Asked in companies
AccentureTata CommunicationsAmazon

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 )
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.
Full screen
Console