You are given a text T and a pattern P.
Let the set S be such that it contains all the starting positions of occurences of pattern P in T. (1 - indexed).
For example if T = aaaa and P = a than S = {1,2,3,4}.
If T=abab and P = ab than S = {1,3}.
You have to find out the number of ways to choose some numbers from the set S such that the product of chosen numbers is divisible by all the numbers from 1 to 9 modulo 10^9+7.
I am unable to approach this question…
what problem are you facing in the question please explain. You just find the number of sets from the set S such that the product of all the numbers in this set is divisible by … (as said above)
Also this question is not related this topic, you should questions with the related topic itself.
Actually I am not understanding the question…Can u please explain the whole question…And actually I am not getting the question so unable to find out the solution…thats why I thought maybe this question is asked from this topic…please explain me the question and how to approach it
Can I get some hint of the solution that is from which topic it is related to?
Lets this example T = abab , P = ab,
so the pattern “ab” is present in T from (1,2) and (3,4) indexes (index here taken as start from 1)
so the Set S = {1, 3} i.e. the starting positions where the pattern is present in S. but here as you can see any subsets of numbers when taken from this, then all numbers of that subset are when multiplied then the product must be divisible by all from 1 to 9.
For solving this, you can first form the set S, then from set S you can make all possible subsets and then check the divisibility condition on them.
Then just return the count of the subsets for which it is satisfied.
Hope you got what the question is and what we have to
Sir can u explain this line once again with an example please…
but here as you can see any subsets of numbers when taken from this, then all numbers of that subset are when multiplied then the product must be divisible by all from 1 to 9.
and also can u suggest me the topic part from which this question has been asked…so I can refer the videos
for this example the subsets will be {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {2,3,4}, {1,3,4}, {1,2,3,4} so you can calculate the mulltiplication of all elements for every subset and check if the product is divisible by all the number from 1 to 9.
That modulo value is just to avoid Datatype overflow
okay okayy …now Its clear to me but from 1 to 9 there are also 4 prime numbers so no subset will be found which is divisible by all the numbers from 1 to 9,isnt it?
In the above example it is true, but if the subset contains the elements then it is possible
yaa…correct…U gave a lot of effort to make me clear…thanks a .lot