RelativelyPrimeSubset
SRM 547 · 2011-11-22 · by sdya
SRM 547 · 2011-11-22 · by sdya · Dynamic Programming, Recursion
Problem Statement
Problem Statement
You are given a int[] S containing a set of pairwise distinct positive integers.
Return the size of the largest subset T of S such that any two numbers from T are relatively prime.
Notes
- Two integers A and B are relatively prime if and only if their greatest common divisor equals to 1.
Constraints
- S will contain between 1 and 50 elements, inclusive.
- Each element of S will be between 1 and 100, inclusive.
- All elements in S will be distinct.
Examples
0)
{2,3,7,11,4}
Returns: 4
One such subset T is {2,3,7,11}, another is {3,4,7,11}.
1)
{4,8,12,16}
Returns: 1
2)
{100,17,81,82}
Returns: 3
3)
{2,3,4,5,6}
Returns: 3
4)
{1,7,49,14}
Returns: 2
Submissions are judged against all 123 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RelativelyPrimeSubset with a public method int findSize(vector<int> S) · 123 test cases · 2 s / 256 MB per case