How to approach Divisible Patterns? [dp]

#1

so my approach is to first apply KMP algo to find occurence of pattern and then using recursion countion for products.

link: https://ide.codingblocks.com/s/254441

#2

@dhruv.160410116084
You don’t need to check for prod%m for 1<=m<=9. Just check for prod%5, prod%7, prod%8 and prod%9, Instead do prod%2520 (578*9=2520). This will cover all cases.
So change line 50 to if(prod % 2520 == 0) and
line no 57 to return (solve(list,i+1, (prod * list.get(i))%2520) + solve(list,i+1,prod)) % 1000000007;

#3

it works , but it gives run error for one test case

#4

@dhruv.160410116084
Try to use dp with memoization. dp size should be dp[1001][2520];

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.