How is the answer 4 of the sample test case

#1

i mean we have 1, 2 ,3 ,4,5 ,6 ,7 and their is only 1 way that product is divisible from 1 to 9 so how is the answer 4

#2

Hey @aryan_007
We will have 1,2,3,4,5,6,7 in our set
So if we take {3,4,5,6,7} then their product is 2520 which is divisible by all nos from 1 to 9
now for 1,2 we have 2 choices for both either to take them or leave them.
So 2*2=4 and thus we have 4 ways .
I hope this resolved ur query .

#3

ohhh okayyyy , so if i have found the numbers then how to find the important numbers to take so that in rest of the numbers i an apply ( take or not take )

#4

@aryan_007
Check this out : Not able to get the approach. Stuck!

#5

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

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
what is the meaning of these 4 lines

#6

@aryan_007
Forget that
Store the occurences of pattern in S in some array ‘ind’.
Now after generating the ind array u have to find the number of subsets which have product divisible by 2520(lcm of 1-9) .
So dp matrix will be of size int dp[10001][2520]
Reccurence relation:
solve(ind,i,prod)= solve(ind,i+1, (prod * ind(i))%2520) + solve(ind,i+1,prod)
I hope you got the approach now. :slight_smile:

1 Like
#7

yaaaaaaaaaaaaaa yaaaaaa i got the logic now

#8

but when i am writing code then getting 0 as the output , i tried to drop the stack trace but still can’t find the bug . https://ide.codingblocks.com/s/318847

#9

Hey @aryan_007
Problem is with your dp array
Problem is with you resizing of 2D array ,values are not getting initialized to -1 ,u have to resize inner and outer vector separately
like this

dp.resize(n+3);
for(int i=0;i<n+3;i++){
dp[i].resize(2523,-1);
}

Now it should work.

#10

but we need n+3 rows and 2523 columns naa ??

#11

Yup and the above matrix will have n+3 rows and 2523 as column size
You can check by printing matrix dimensions :(dp.size(),dp[0].size())

#12

got TLE in 1 case !!

#13

Hey @aryan_007
Remove idx.clear() & dp.clear() those are extra computations.
And your code should work fine .:slight_smile:
Please do not forget to mark this as resolved.

1 Like
#14

yes sir , it got AC but why this happened !! are these that costly operations !!

#15

Constraint must be tight ,so those are just extra computation which I asked you too remove :slight_smile:

#16

okay sir , thankyou sir !!!

1 Like