Please help me in getting the recurrence relation/approach for this problem.
Not able to get the approach. Stuck!
@zanj0
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}
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