MixedUpPrimes
TCCC06 Sponsor Qual · 2006-08-22 · by AdminBrett
TCCC06 Sponsor Qual · 2006-08-22 · by AdminBrett · Dynamic Programming, Math, Recursion, String Parsing
Problem Statement
Problem Statement
Using the operators '+', '-', '/', '*', and parentheses as many times as you wish, find expressions for the smallest and largest primes that use each element of values exactly once. A prime is an integer greater than 1 with no divisors except 1 and itself. Return a int[] with exactly two elements, where the first element is the smallest prime you can make, and the second is the largest. If no primes can be constructed, return an empty int[] .
Notes
- The division operator truncates its results. For example, 8/5 = 1.
- The given numbers cannot be concatenated. For example, 8 and 5 cannot be combined to form 85.
Constraints
- values will contain between 1 and 6 elements, inclusive.
- Each element of values will be between 1 and 30, inclusive.
Examples
0)
{1,2}
Returns: {2, 3 }
We get 2 using 2*1. We get 3 using 2+1.
1)
{1,2,3}
Returns: {2, 7 }
Here we use 3-2+1=2 and 3*2+1 = 7.
2)
{1,2,3,4,5,6}
Returns: {2, 719 }
3)
{2,3,5,7,11,13}
Returns: {2, 15017 }
4)
{2,13,19,29,23,7}
Returns: {2, 1153241 }
Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MixedUpPrimes with a public method vector<int> findPrimes(vector<int> values) · 55 test cases · 2 s / 256 MB per case