CODEWITHSUNDEEP
arraysmathcombinatorics
rahulGupta
rahulGupta

Reputation: 41

Recover Original Array when GCD of all the subsets of the array is given

Suppose an array originally contains N elements. Now GCD of all the subsets is taken and another array of size 2N - 1 is generated. Now given the array having GCD of all the subsets, how can we obtain the original array?

Upvotes: 1

Views: 151

Answers (1)

Brett Hale
Brett Hale

Reputation: 22328

If we exclude the empty set {} and the N sets with a single element {xi}, which have no gcd - assigning these the value (xi) trivially solves the issue - then it's easy to show a counter example where the original values cannot be recovered:

Consider: {2, 4, 8} subsets: {}, {2}, {4}, {8}, {2, 4}, {4, 8}, {8, 2}, {2, 4, 8}. Excluding the empty set {}, and a definition where: gcd{xi} is defined as: gcd(xi, 0) (which trivially yield the N values) then there are 2^N - 1 - N gcd values: (2, 4, 2, 2) respectively.

Now consider the distinct primes: p0, p1, p2, and the set {2.p0, 4.p1, 8.p2}. The gcd for subsets with more than one element with the ordering above will still be: (2, 4, 2, 2). There is no way to recover the prime factors here - so the original values cannot be found.

Upvotes: 2

Related Questions