Hacker blocks doubt

#1

https://hack.codingblocks.com/app/practice/5/1342/problem

Please give me some hint for this problem

#2

hello @Somasree
are u familiar with dp with bitmasking?

#3

I find this topic very difficult.

#4

…

you should know about dp and bitmasking very well to solve such problem .

adding a video link pls go through it for clarity on bitmasking->

#5

I have watched the video .Now can you plz give me some hint refrading the problem

#6
  • Since there are 15 primes only, consider a 15-bit representation of every number where each bit is 1 if that index of prime is a factor of that number. We will index prime numbers by 0 indexing, which means 2 at 0th position 3 at index 1 and so on.
  • An integer variable ‘ mask ‘ indicates the prime factors which have already occurred in the subset. If i’th bit is set in the mask, then i’th prime factor has occurred, otherwise not.
  • At each step of recurrence relation , the element can either be included in the subset or cannot be included. If the element is not included in the subarray, then simply move to the next index. If it is included, change the mask by setting all the bits corresponding to the current element’s prime factors, ON in the mask. The current element can only be included, if all of its prime factors have not occurred previously.
  • This condition will be satisfied only if the bits corresponding to the current element’s digits in the mask are OFF.

dp[i][j], i is the position of the element in the array, and j is the mask.
dp[i][j] = inlcude ith element if possible + dp[i+1][updated mask]
or
exluce ith element dp[i+1][j]

take max of these two cases