TopCoder problem "Indivisible" used in TCCC05 Wildcard (Division I Level Two)



Problem Statement

    

Given a positive integer n, you are to find the largest subset S of {1,...,n} such that no member of S is divisible by another member of S. If there is more than one subset of the maximum size, choose the lexicographically earliest such subset. A subset S is lexicographically earlier than a subset T if the smallest element that is a member of one of the subsets, but not both, is a member of S. Return the subset S as a int[] in increasing order.

 

Definition

    
Class:Indivisible
Method:largestSubset
Parameters:int
Returns:int[]
Method signature:int[] largestSubset(int n)
(be sure your method is public)
    
 

Constraints

-n is between 1 and 1000, inclusive.
 

Examples

0)
    
10
Returns: {4, 5, 6, 7, 9}
There are several possible subsets of size 5, such as { 4,6,7,9,10 }, but { 4,5,6,7,9 } is the lexicographically earliest.
1)
    
1
Returns: {1}
2)
    
5
Returns: {2, 3, 5}
3)
    
24
Returns: {4, 6, 9, 10, 11, 13, 14, 15, 17, 19, 21, 23}

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3957

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6553&pm=3957

Writer:

vorthys

Testers:

PabloGilberto , lbackstrom , Yarin

Problem categories:

Greedy