PrimePairs

TCO09 Qual 1 · 2009-02-24 · by legakis

TCO09 Qual 1 · 2009-02-24 · by legakis · Dynamic Programming

Show categories

Class Name: PrimePairs

Return Type: int[]

Method Name: matches

Arg Types: (vector<int>)

Problem Statement

You wish to group a list of numbers into pairs such that the sum of each pair is prime. For example, given the numbers { 1, 4, 7, 10, 11, 12 }, you could group them as follows:

1 + 4 = 5
7 + 10 = 17
11 + 12 = 23

or:

1 + 10 = 11
4 + 7 = 11
11 + 12 = 23

Given a int[] numbers, return a int[] of all the elements in numbers that could be paired with numbers[0] successfully as part of a complete pairing, sorted in ascending order. Note that in the example above, even though 1 + 12 is prime, there would be no way to pair the remaining 4 numbers. So the answer for the example above would be { 4, 10 }.

Notes

A prime number is a number divisible only by 1 and itself.

Constraints

numbers will contain an even number of elements, between 2 and 50, inclusive.
Each element of numbers will be between 1 and 1000, inclusive.
Each element of numbers will be distinct.

Examples

{ 1, 4, 7, 10, 11, 12 }
Returns: {4, 10 }

This is the example from the problem statement.

{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
  11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
  21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
  31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
  41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }
Returns: {2, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, 40, 42, 46 }

{ 347, 149, 331, 120, 96, 804, 294, 918, 35, 191,
  925, 234, 739, 197, 715, 777, 931, 894, 982, 969,
  637, 349, 732, 424, 751, 556, 752, 369, 546, 211,
  952, 405, 815, 862, 443, 230, 356, 238, 148, 694,
  11, 967, 161, 467, 524, 65, 904, 377, 605, 444 }
Returns: { }

{ 14, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18 }
Returns: {3, 5, 9, 15, 17 }

{ 931, 242, 419, 620, 321, 146, 755, 90 }
Returns: {90 }

{ 11, 1, 4, 7, 10, 12 }
Returns: {12 }

The same numbers, but in a different order. In both of the 2 possible complete pairings, the 11 is paired with the 12.

{ 8, 9, 1, 14 }
Returns: { }

No complete pairings are possible because none of the numbers can be paired with 1.

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

Coding Area

Language: C++17 · define a public class PrimePairs with a public method vector<int> matches(vector<int> numbers) · 159 test cases · 2 s / 256 MB per case