AllButOneDivisor
TCO11 Qual 3 · 2011-05-07 · by vexorian
TCO11 Qual 3 · 2011-05-07 · by vexorian · Simple Math, Simple Search, Iteration
Problem Statement
Problem Statement
You are given a int[] divisors containing K elements. Find a positive integer n such that exactly K-1 elements of divisors are exact divisors of n. If there are several such numbers n, return the smallest possible one. If no such number n exists, return -1 instead.
Notes
- A number x is an exact divisor of y if y divided by x yields an integer result.
- If x is an exact divisor of y then we call y a multiple of x.
Constraints
- divisors will contain between 2 and 6 elements, inclusive.
- Each element of divisors will be distinct.
- Each element of divisors will be between 1 and 15, inclusive.
Examples
0)
{2,3,5}
Returns: 6
There are many possible values for n in this case. For example: 6, 15, 75 and 12. 6 is the smallest of them.
1)
{2,4,3,9}
Returns: 12
2)
{3,2,6}
Returns: -1
Every multiple of 3 and 2 is also a multiple of 6. Every multiple of 6 is also a multiple of 2 and 3. Therefore, a number that is a multiple of exactly 2 out of the three elements in this array cannot exist.
3)
{6,7,8,9,10}
Returns: 360
4)
{10,6,15}
Returns: -1
19)
{2,3,5,6}
Returns: 6
It is best to remove 5 instead of 6 (the maximum)
Submissions are judged against all 134 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class AllButOneDivisor with a public method int getMinimum(vector<int> divisors) · 134 test cases · 2 s / 256 MB per case