Divisible patterns : 2D DP

#1

Didn’t understood the sample test case and the approach towards the question

#2

Hey @aman2382000
For sample test case :
set S is { 1, 2, 3, 4, 5, 6, 7 }
Divisible by all means the product of chosen subset should be divisible by numbers from 1 upto 9

To make a number divisible by all numbers from 1 to 9 product should have 2^3, 3^2, 5, 7 as factors.

Ans is 4 because :
{ 5, 7, 2, 4, 3, 6}
{ 5, 7, 4, 3, 6}
{ 1, 5, 7, 2, 4, 3, 6}
{ 1, 5, 7, 4, 3, 6}

Please try to figure out the approach once now. If you can’t then we can discuss the solution the next time you message on this doubt.

#3

Got the intution of the problem but unable to approch the solution.

#4

@aman2382000
A number can be in 1 of 48 possible states
4 states of 2 that are ( 2^0, 2^1, 2^2, 2^x x>=3 ) as factors
Similarly 3 states for 3 and 2 states for 5 and 7

So if we have 10 its state will be [1,0,1,0] (2,3,5,7)

After creating these states divide the states into 2 halves each with 24 states
For each create all subsequences with possible states as part of product

Then you have 2 sets of states
Find counterpart of a state in 1st set in the 2nd

1 Like
#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.

#6

I like your aproach,but feeling difficulty in implementation,
Can you explain this lines bit more.
> After creating these states divide the states into 2 halves each with 24 states
> For each create all subsequences with possible states as part of product