Given a non negative array, find the number of subsequences having product smaller than K.

k<10^2 arr.size<10^3

Examples:

Input : [1, 2, 3, 4]

k = 10

Output :11

The subsequences are {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {1, 2, 3}, {1, 2, 4}

Input : [4, 8, 7, 2]

k = 50

Output : 9

I think the brute-force solution may work. Any judge to submit?

If the size is more then what to do other than brute-force?

I don't know about the exact time complexity of brute-force solution but the solution mentioned by -Morass- is correct and works in O(n*k).

Here, since input size is less than or equal to 1000, we can just consider all the subsequences and find the product of each of them. For example, we fix a left point on the array, and for that keep extending the right endpoint, unless we exceed K. The number of times we can shift the right endpoint is the number of possible right endpoints if the left endpoint is fixed at the index where we had initially done. Now, just iterate over all possible left endpoints.

complexity: o(n^2).

A better solution would be to use a 2 pointer type algorithm. Here, observe that if we already have a subsegment whose product exceeds K, then if we multiply more elements, it will still always exceed K. Thus, we need to divide some previous elements first. So to do this, start the left and right endpoints at 0. Then keep moving the right endpoint and keep multiplying the new elements. Each time you are able to do so without exceeding K, increase ctr. Now, if the product exceeds K, then start shifting the left endpoint and divide the product that you had, with the element the left endpoint is processing, until the product again becomes lesser than K. Now, again start shifting the right endpoint and increasing ctr as before.

complexity: o(n) [since the right endpoint shifts at most n times and so does the left.]

Subsequence

ohkk.. then let me edit it. sorry, my bad.

Good day to you,

Well, since the

Kis pretty low, the easiest approach might (imho) be 2D Dynamic Programming, where first dimension is index of array and second is product. In each DP-state you either try to "multiply" by current number or simply go to next-number.In recursive form, it might look like:

I guess some memorisation + some modulo (etc.. sauce) will be necessary, yet I'm sure you'll deal with it.

Good Luck & Have Nice Day!

*memoization

Right, thank you ^_^

can we do it by bottom up approach?

For iterative approach, simply "reverse" what you are asking for:

so instead of

you will iterate from back and ask for

which is (as you can see) almost the same.

The "ifs" ending the recursion can be done either by "pre-filling" of the table, yet in case of "multiplication" a would rather recommend to do them by ifs again.

so basicaly it is same, yet instead if recursion, there is:

Let

zbe the number of zeros in the array andnbe the total number of elements. There are (2^{z}- 1)·2^{n - z}subsequences with product 0. Remove all zeros now and operate on the remaining array.We do something similar to what -Morass- described. Let

small(i,j) denote the number of subsequences of the firstielements with product at mostj. It's a simple DP, but we do this only for . Likewise, definelarge(i,j) such that the product is required to be at most . Again, we do this for .It's easy to deduce the following formulas now:

The final answer

large(n, 1) is obtained in time.I tried to implement this: Code. Just tested on your samples and only for small answers (no modulo).

its just a variation of normal knapsack. each cell will have value equals :

for(int i = 1 ;i<=k ;i++) for(int j = 1 ; j <=n ;j++){ if(arr[i-1] < j){ dp[i][j] = dp[i-1][j/arr[i-1]] + dp[i-1][j] + 1; } else dp[i][j] = dp[i-1][j]; } where i represents the arr of numbers and j represents the product.

the final answer will be dp[k][n];