CODEWITHSUNDEEP
pythonalgorithmsubsetdynamic-programminggreatest-common-divisor
Joshin Rexy
Joshin Rexy

Reputation: 23

Number of ways we can partition a set into two subsets such that the GCD of product of the elements in both subsets is minimum

We have a set or a unique list of positive integers with constraints that the size of the list or set can go up to 10000. The objective is to divide the list into 2 non-empty subsets such that the GCD(Prod1, Prod2) == 1, where Prod1 is the product of all the elements in subset 1 and Prod2 is the product of all the elements in subset 2.

For e.g.

Input:

5 1 2

Output:

6

6 subsets that satisfy the condition

{1}, {2, 5} = gcd(1, 10) = 1
{1, 2}, {5} = gcd(2, 5) = 1
{1, 5}, {2} = gcd(5, 2) = 1
{2, 5}, {1} = gcd(10, 1) = 1
{5}, {1, 2} = gcd(5, 2) = 1
{2}, {1, 5} = gcd(2, 5) = 1

Input:

2 3 6

Output:

0

As there are no subsets that satisfy the condition

I tried brute force approach by generating all 2-way partitionings and finding its products, then taking its gcd. but obviously, this takes at least O(N^2) or more and so much memory which is not feasible considering the constraints. Is there any better approach using Dynamic Programming just like in subset-sum/difference question or using any other algorithm/data structure?

Upvotes: 1

Views: 442

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

As Michael Butscher observes, every two positive integers that are not relatively prime must be on the same side of the partition. This turns out to be a sufficient as well as necessary condition.

Make a graph whose vertices are the given positive integers and whose edges indicate pairs of integers that are not relatively prime. Count the number of connected components k in this graph. Return 2k − 2 since independently, each component can be on the left side of the partition or the right, minus the 2 degenerate partitions where every component is on the same side.

Upvotes: 1

Related Questions