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