This problem was asked in BuyHatke’s online coding round held today morning.
Given an array A of length N. We need to build a multiset M, such that if any two elements of M are multiplied, the product should not be a cube. Return the maximum size of M.
1 <= Ai <= 10^5
Example- A=[1 , 2 , 4]. One possible M=[1,2]. Multiplication of 1 and 2 does not give a cube number.
Unfortunately, the constraints were not mentioned in the problem statement, but some participants assumed to be N <=22. I could just get partial points by bruteforce. For full points, it can be solved by the concept of Maximum Independent Set . Can anyone explain his approach for this and some similar problems on this concept?
Here’s the image for convenience
Could you send the link of the problem
It was held privately on InterviewBit, so I can’t find the link now, as the test link is inactivated now
What are the constrains for elements of A
Updated the problem with image
I also could not solve this. Could anyone help?
I think this can work,
Store the count of prime factorisation of all the no.s in the 2 d array of dimension [22][9000] (22 for No. Of elements in A , 9000 for no. Of prime no.s till 100000) then for all no.select every no. And Check whether the addition of the no. Of prime factor with eavery other no in array will be a divisible of 3 or not if it is then don’t add that no. And if it will be then increment the count for that no.
For eg.
When A={4,12,3,9} explaining for the case of 4,
Put 4 in the vector, when 4 is there ,Store their prime factorisation ,
And then for prime factor of 4 i.e 2 appear 2 time , check that for 12 does it makes the appearance of any no. Divisible by 3, for (2) total appearance will be 4 and for (3) it will be 1 , so add 12 in the vector which contains 4 , now for 3 check whether it makes appearance divisible by 3 for 4 and 12 of all prime factor and for 9 check it for 4,12,3 and since 9 makes it with 3 so don’t push 9 in it .
Check it for 3,9,12 as well
Total complexity would be O(N^3) I think
I know you will not be able to understand it as this time I am not able to explain the approach nicely so , just a hint try thinking in terms of prime factors of each no.But still hoping that it helps
I am a little confused about your approach. Suppose A= [1,2,4, 16] . I think, this fails for this tc if I am not wrong. Can you please elaborate the approach if possible?
First [no. writeen in () is the power corresponding to the previous no.)]
Take 1 push it in a vector, check whether prime factor of 2 i.e 2 appear how many time in 1 and 2 , it appear one time so push 2 in the vector , take 4 check prime factor of 4 i.e 2( 2 ) , check how many times it appears with 1 it is 2 , check how many time it appear with 2, it is 3 since 3 is divisible by 3 so, don’t push 4 . Take 16 check prime factor of 16 i.e 2( 4 ) how many times it appears in 1 , so it appears 4 time ,check how many time it appear with 2, it appear 5 times , so push 16
In this way As I started with 1, you will have to start with every other no. , OR you can start with every other no. Which is not included in the previous vectors , And then take the size of the vector with maximum elements and that will be the answer and in this case it is [1,2,16] vector with size 3, . In worst case it’s of O(N^3) and in best case O(N^2)
Oh I forgot to mention, there is an exception of 1 , as 1 is a cube so it should not appear twice in the vector , and one more thing while checking that appearance is divisible by 3 or not also check that it is not equal to zero
I think the approach for maximum independent set is as follows:
For every 2 numbers check if their product is a perfect cube, if it is then make an un-directed edge between them, In this way you end up with a graph where you have to find the size of Maximum Independent Set…
2 Likes
Can you provide some code of your approach??
Okk, I will try to post it before tomorrow morning
I don’t think so that fixing a element in the desired group and then calculation of max size by O(n^2) would be optimal.
Consider fixing an element X then adding Y to your vector just after X, Now let there be three numbers p,q,r that forms a cube with Y, now since you already added Y you can’t add p,q,r. So it would have been better to not add Y even if it was in compliance with the current subset. Also, this ambiguity might occur multiple times after fixing an element.
Could you explain more clearly how you would handle this inexactness?
I wrote the complexity is O (N^3) , and for your example we will do it for all elements that are X,Y,P,Q,R
And I am not saying that it is 100% correct as I didn’t got the questions link so I have not submitted it
Yeah i said the same fixing one element then O(n^2) for every fix, would result in O(n^3), i get that part. It’s your linear ordering and pushing elements into vector and then not removing it later if required that will cause trouble in further sub-problem.
Anyway, I am looking forward to test your code. Hope you will drop it soon.
Okkk, will surely try to drop it before tomorrow’s morning.
@mohittkkumar @samarth2017 here is the code of my approach , would be happy to know where it fails if it fails
#include<bits/stdc++.h>
using namespace std;
int pr[24][9000]={0};
void prime(int x,int j)
{ int i;
for(i=2;i*i<=x;i++)
{
while(x%i==0)
{
pr[j][i]++;
x/=i;
}
}
if(x>1)
pr[j][x]++;
}
#define pb push_back
int main()
{
int n;
map<int,int> m;
cin>>n;
int a[n+1];int i,j,k;
for(i=1;i<=n;i++)
{cin>>a[i];
prime(a[i],i);
m[a[i]]=i;
}
vector<int> v;int l;int flag=0;int ans=0;int flag1=0;
for(k=1;k<=n;k++)
{ v.pb(a[k]); if(a[k]==1) flag1=2;
for(i=1;i<=n;i++)
{ if(i!=k)
{ flag=0;
if((a[i]==1)&&(flag1==2)) continue;
for(j=0;j<v.size();j++)
{ int z=m[v[j]];
for(l=2;l<=9000;l++)
{
if(((pr[z][l]+pr[i][l])%3==0)&&((pr[z][l]+pr[i][l])!=0))
{flag=1;break;}
} if(flag==1) break;
}
//cout<<i<<" "<<flag<<"\n";
if(flag==0) v.pb(a[i]);
}
} //cout<<k<< " "<<v.size()<<"\n";
if(v.size()>ans) ans=v.size();
v.clear();
}
cout<<ans;
return 0;
}
It is an optimisable code i.e in place of going for all the prime no. you can go for only those prime no. that are in the prime factorisation of the two no.s.
edit: how to format the code? as this the first time i am uploading a code
Please format it using ```
