Count Number of Subsequences Problem Statement
Given an array of non-negative integers A
and an integer P
, determine the total number of subsequences of A
such that the product of any subsequence does not exceed P
.
Explanation
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.
Input
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
For each test case, print an integer denoting the count of subsequences with a product not exceeding P
. Print the result for each test case on a new line.
Example
Input:
A = [1, 2, 3], P = 4
Output:
5
Explanation:
All the subsequences are {1}, {2}, {3}, {1,2}, and {1,3} with products not exceeding 4. Thus, the count is 5.
Constraints
1 <= T <= 10
1 <= N <= 10^3
1 <= A[i] <= 10^3
1 <= P <= 10^3
- The sum of
N
over all test cases is <= 10^3.
Note
- Your solution should compute results modulo 109 + 7.
- No need to handle input/output as it's taken care of; implement the function directly.
AnswerBot
4d
Count the number of subsequences of an array with product not exceeding a given value.
Iterate through all possible subsequences of the array
Calculate the product of each subsequence and check if it ex...read more
Help your peers!
Add answer anonymously...
Top Wipro Project Engineer interview questions & answers
Popular interview questions of Project Engineer
Top HR questions asked in Wipro Project Engineer
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app