Count Number of Subsequences
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

Question

Count Number of Subsequences

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 <= 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

Accepted Answer

One must master Fundamentals of Programming in any 1 programming language of his/ her choice. Here are the topics to master.
* Arrays
* Strings
* Decision Making
* Looping
* Functions

Accepted Answer

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.

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:

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.
If ‘IDX' >= 'N’ return 0.
Return ‘CNT’.

Space Complexity: O(1)Explanation:

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).

Time Complexity: O(2^n)Explanation:

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.

Accepted Answer

Dynamic Programming

In the recursive approach, some subproblems are solved again and again.

Let us see the recursion tree for ‘A’ = [1,2,3] and ‘P’ = 4.

It is clear from the recursion tree that the function for (4, 2, 2) is called two times. So to solve this problem of overlapping subproblems, we will use Dynamic programming.

Approach: The basic idea is to use a 2-D array ‘DP’ with ‘P + 1’ rows and ‘N + 1’ columns where a row represents the different values of ‘P’ and column represents the maximum number of elements taken from the array.

Take a 2-D array ‘DP[ P + 1 ][ N + 1 ]’ and initialize its values to 0.
We will run two loops ‘i’ from 1 to ‘P + 1’ and j from 1 to ‘N + 1’.
‘DP[ i ][ j ]’ stores the count of subsequences having product not more than ‘i’ by taking ‘j’ number of elements from ‘A’.
‘DP[ i ][ j ]’ = count of subsequences having the product, not more than ‘i’ by taking ‘j - 1’ number of elements + count of subsequences formed using ‘ jth ’ element.
Count of subsequences by taking ‘j - 1’ number of elements can be found simply at ‘DP[ i ][ j - 1 ]’. So ‘DP[ i ][ j ]’ = ‘DP[ i ][ j - 1 ]’.
Now if ‘A[ j - 1 ]’ <= ‘i’
- ‘DP[ i ][ j ]’ = ‘DP[ i ][ j ]’ + ‘DP[ i / A[ j-1 ] ] [ j-1 ]’.
- It means we have taken jth element in subsequence and added the count of subsequences with product less than ‘i’ / ‘A[ j - 1 ]’ i.e. ‘DP[ i / [ A ] [ j -1 ]] [ j-1 ]’ .
- Add 1 to ‘DP[ i ][ j ]’ for a subsequence of only the ‘jth’ element.
Return ‘DP[ P ][ N ]’.

Algorithm:

Initialize a 2-D array ‘DP’ of ‘P’ + 1 row and ‘N’ + 1 column.
Run two loops - ‘i’ from 1 to ‘P’ and ‘j’ from 1 to ‘N’.
Store previous result to ‘DP[i][j]’ = ‘DP[i][j - 1]’.
If( ‘A[j - 1]’ <= ‘i’) then ‘DP[i][j]’ equals ‘DP[i][j]’ + ‘DP[ i / A[j - 1] ][ j - 1 ]’ +1.
Return ‘DP[P][N]’.

Space Complexity: OtherExplanation:

O(P * N), where N is the number of elements in array A and P is the product given.

We have used a 2-D array of size P * N. Therefore space complexity is O(P * N).

Time Complexity: OtherExplanation:

O(P * N), where N is the number of elements in array A and P is the product given.

As we compute the value of every element of the 2-D array, so the time complexity is equal to the total size of ‘DP’ array i.e ‘P * N’.

Python (3.5)

'''
    Time Complexity : O(P * N)
    Space Complexity: O(P * N)

    Where 'N' is size of Array and 'P' is Product value.
'''

mod = 1000000007

def countSubsequences(a, n, p):

    # 2D array to store result.
    rows = p + 1
    cols = n + 1

    # Set values of 'DP' to '0'.
    dp = [[0 for i in range(cols)] for j in range(rows)]

    for i in range(1, p + 1):

        for j in range(1, n + 1):

            # Store result of 'j - 1' elements.
            dp[i][j] = dp[i][j - 1] % mod

            # Check whether to include 'j'th element or not.
            if (a[j - 1] <= i and a[j - 1] > 0):

                # Count of subsequences by taking 'j'th element.
                dp[i][j] = (dp[i][j] + dp[i // a[j - 1]][j - 1] + 1) % mod

    # Result is stored at 'DP[P][N]'.
    return dp[p][n]

C++ (g++ 5.4)

/*

    Time Complexity : O(P * N)

    Space Complexity: O(P * N)



    Where 'N' is size of Array and 'P' is Product value.

*/



#define mod 1000000007



int countSubsequences(vector < int > & a, int n, int p) {



    // 2D array to store result.

    int dp[p + 1][n + 1];



    // Set values of 'DP' to '0'.

    memset(dp, 0, sizeof(dp));



    for (int i = 1; i <= p; i++) {

        for (int j = 1; j <= n; j++) {



            // Store result of 'j - 1' elements.

            dp[i][j] = dp[i][j - 1] % mod;



            // Check whether to include 'j'th element or not.

            if (a[j - 1] <= i && a[j - 1] > 0) {

                //Count of subsequences by taking 'j'th element.

                dp[i][j] = (dp[i][j] + dp[i / a[j - 1]][j - 1] + 1) % mod;

            }

            

        }



    }



    // Result is stored at 'DP[P][N]'.

    return dp[p][n];

}

Java (SE 1.8)

/*
    Time Complexity : O(P * N)
    Space Complexity: O(P * N)

    Where 'N' is size of Array and 'P' is Product value.
*/

public class Solution {

    private static int mod = 1000000007;

    public static int countSubsequences(int[] a, int n, int p) {

        // 2D array to store result.
        int[][] dp = new int[p + 1][n + 1];

        for (int i = 1; i <= p; i++) {
            for (int j = 1; j <= n; j++) {

                // Store result of 'j - 1' elements.
                dp[i][j] = dp[i][j - 1] % mod;

                // Check whether to include 'j'th element or not.
                if (a[j - 1] <= i && a[j - 1] > 0) {
                    //Count of subsequences by taking 'j'th element.
                    dp[i][j] = (dp[i][j] + dp[i / a[j - 1]][j - 1] + 1) % mod;
                }
                
            }

        }

        // Result is stored at 'DP[P][N]'.
        return dp[p][n];
    }
}

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’.

Note

For Example

Input Format

Output Format

Note

Constraints

Top Wipro Project Engineer interview questions & answers

Popular interview questions of Project Engineer

Top HR questions asked in Wipro Project Engineer