Connection Status:
Competition Arena > FewestFactors

FewestFactors

SRM 272 · 2005-11-19 · by gepa

SRM 272 · 2005-11-19 · by gepa · Brute Force, Simple Math
Class Name: FewestFactors
Return Type: int
Method Name: number
Arg Types: (vector<int>)
Problem Statement

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.

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
11)
{2, 4}
Returns: 24

Both 24 and 42 have 8 factors (24 has the factors 1, 2, 3, 4, 6, 8, 12 and 24, while 42 has the factors 1, 2, 3, 6, 7, 14, 21 and 42). In this case we have to use the tie-breaker and return

34)
{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).

Submissions are judged against all 87 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FewestFactors with a public method int number(vector<int> digits) · 87 test cases · 2 s / 256 MB per case

Submitting as anonymous