Question

Media.net | OA | Oct 2022 | Set - 3

Answer 1

Question asked :

Problem: We are familiar with primes. Here we define omega prime.

A number X is an omega prime such that any perfect square of Y (Y > 1) doesn't divide X, such as 2 and 6 are omega primes while 12 is not an omega prime since it can be divided by 2*2. Now we are given an array A of integers, we need to find out the total number of subsets such that the product of elements of the subset is omega prime. The answer can be huge, hence output modulo 1000000007.

1 <= A.size() <= 2 * (10^4)

1 <= A[i] <= 30

Answer 2

Sol : 

Lets exclude 1 for now. Now, we have 18 such "omega prime" numbers. now we see which subsets can form omega prime numbers, which can be done in 2^18. Now for each valid subset we just have we just multiply their counts (as we can only include one of each type). And to include 1, in each valid subset we just multiply it by 2^(count of 1)

Any number can be expressed as product of some power of primes. Now omega prime is such a number in which the power of any prime can be atmost 1 (if it's 2 or greater, it will be divisible by the square of that prime). Now there are 10 primes in the range [1,30]. So we can solve this using bitmask dp (dp[i][mask]), where mask will denote which primes have already been taken till the ith element of the array.