Is it a 0/1 knapsack problem ?

general
,
1

I recently come by this question. You are given an array of size n and an integer k. You need to find the total number of subsequences whose product of elements ends with digit k.

Ex: arr=[1,2,3,7,7,7] k=3
[1,3] ,[7,7,7] ,[7,7,7,1] and [3] are 4 subsequences whose element’s product end with digit 3.

[7,7,7]=>7X7X7=343

Constraints:
0<=k<=9
1<=n<=10^5

2

Not exactly 0/1 knapsack but you can do the following dp

\text{dp}[i][j] \leftarrow Number of subsequences whose product have last digit as i using digits 0,1, \dots j.

Final answer would be \text{dp}[k][9]. Transitions are trivial.

You can also do some divide and conquer as well to do the same thing.

2 Likes
3

It is similar but not exactly 0/1 knapsack. We need to note that only the last digit of the product matters. Therefore we can maintain dp[N][10], where dp[i][j] is number of subsequences of A[:i] with product ending with digit j.

Transition :

for (int i = 1; i <= N; ++i) {
    for (int j = 0; j < 10; ++j) {
        tmp[(j * A[i]) % 10] += dp[i - 1][j];
    }
    for (int j = 0; j < 10; ++j) {
        dp[i][j] = tmp[j] + dp[i - 1][j];
    }
}

Answer would be dp[N][k]

1 Like
4

Yes thanks man , I got the idea.

1 Like
5

Very clean and simplistic explanation. Thanks a lot, dear.

1 Like