In this post, we are going to solve Omega Primes DSA Problem from MediaNet Online assessment. Let’s have a look at the problem statement first and then try to solve the problem.
Omega Primes DSA Problem Statement
Carl is bored of playing with ordinary prime numbers. Thus, he comes up with some special numbers called Omega Primes.
A number
is called Omega Prime, if there exists no perfect square
such that
divides
.
For example, 6 is an Omega Prime because there is no perfect square except 1 that divides 6.
On the other hand, 12 is not an Omega Prime as 4 (which is a perfect square) is a divisor of 12.
Carl decides to play a bit more with Omega Primes. He has an array
of integers. Carl wants to find the number of different subsets such that the product of elements for each subset, results in an Omega Prime. Help Carl find this number.
Since this number can be large, output the answer modulo
.
The first line contains an integer
denoting size of array
The second line contains
space separated integers, where
integer denotes
Output the answer as described in statement.
3 2 4 3
3
3 2 2 2
3
6 2 30 15 18 24 22
6
Omega Primes DSA Problem Solution C++
#include <bits/stdc++.h>
using namespace std;
int primes[10]={2,3,5,7,11,13,17,19,23,29};
int check(int n)
{
for(int i=0;i<10;i++)
{
if(n%(primes[i]*primes[i])==0)
return 0;
}
return 1;
}
int solve(int ind,vector<vector<int>>&dp,int mask,vector<int>&arr)
{
if(ind>=arr.size())
{
if(mask==0)
return 0;
else
return 1;
}
if(dp[ind][mask]!=-1)
return dp[ind][mask];
int flag=0;
int ans=0;
int pmask=mask;
for(int i=0;i<10;i++)
{
if(arr[ind]%primes[i]==0)
{
if(mask & 1<<i)
{
flag=1;
break;
}
else
pmask=pmask|(1<<i);
}
}
ans=(ans+solve(ind+1,dp,mask,arr))%1000000007;
if(flag==0)
ans=(ans+solve(ind+1,dp,pmask,arr))%1000000007;
return dp[ind][mask]=ans;
}
int main() {
int n;
cin>>n;
vector<int>arr;
for(int i=0;i<n;i++)
{
int a;
cin>>a;
if(check(a))
arr.push_back(a);
}
int sz=arr.size();
vector<vector<int>>dp(sz,vector<int>(1024,-1));
//cout<<arr.size();
cout<<solve(0,dp,0,arr);
return 0;
}