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=34**3**

Constraints:

0<=k<=9

1<=n<=10^5

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

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

Yes thanks man , I got the idea.

1 Like

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

1 Like