TopCoder problem "FewestFactors" used in SRM 272 (Division I Level One , Division II Level Two)



Problem Statement

    

You will be given some decimal digits in a int[] digits. Build an integer with the minimum possible number of factors, using each of the digits exactly once (be sure to count all factors, not only the prime factors). If more than one number has the same (minimum) number of factors, return the smallest one among them.

 

Definition

    
Class:FewestFactors
Method:number
Parameters:int[]
Returns:int
Method signature:int number(int[] digits)
(be sure your method is public)
    
 

Notes

-A factor of an integer n is an integer k, such that n % k = 0 (% being the modulo operator).
-The digit 0 can also be used as a leading zero, see example 1.
 

Constraints

-digits will have between 1 and 5 elements, inclusive.
-Each element of digits will be between 0 and 9, inclusive.
-At least one element of digits will be non-zero.
 

Examples

0)
    
{1, 2}
Returns: 21

Using the digits 1 and 2 we can build the numbers 12 (which has 6 factors: 1, 2, 3, 4, 6 and 12) and 21 (which has 4 factors: 1, 3, 7 and 21). So we return 21, which is the number among them having the smallest number of factors.

1)
    
{6, 0}
Returns: 6

Note that we can use 0 as a leading zero, giving the number 6 that has 4 factors (1, 2, 3 and 6), less than the alternative 60 that has 12 factors.

2)
    
{4, 7, 4}
Returns: 447

Note that digits may contain duplicate digits. We have to use each digit as many times as it appears in the input.

3)
    
{1, 3, 7, 9}
Returns: 1973
4)
    
{7, 5, 4, 3, 6}
Returns: 36457
5)
    
{1,2,4}
Returns: 241
Both 241 and 421 are prime numbers, and thus have exactly 2 factors (241 has the factors 1 and 241, while 421 has the factors 1 and 421). All other numbers that we can build from these digits (124, 142, 214 and 412) have more than 2 factors. We have to use the tie-breaker here and return the smaller of (241, 421).

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8069&pm=5886

Writer:

gepa

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Simple Math