Problem Statement
You are given a set of distinct positive integer values in the
A set of numbers is called nice if each element x of the set has the following property: in the set we can find a different element y such that the sum of x and y is divisible by multiple.
For example, if multiple = 10, the set {1, 9, 19, 29} is nice: for each element x we can find another element y such that x+y is a multiple of 10. However, the set {23, 25, 27} is not nice - note that we cannot pair the 25 with itself.
Find the largest nice subset of values. Return the sum of its elements.
Definition
- Class:
- PairedMultiples
- Method:
- selectedTotal
- Parameters:
- int[], int
- Returns:
- int
- Method signature:
- int selectedTotal(int[] values, int multiple)
- (be sure your method is public)
Notes
- It can be shown that the largest nice subset of values is always unique.
Constraints
- multiple will be between 2 and 100, inclusive.
- values will contain between 2 and 50 elements, inclusive.
- Each element of values will be between 1 and 100, inclusive.
- Each element of values will be unique.
Examples
{ 1, 2, 3, 4, 5 }
3
Returns: 12
The entire set {1, 2, 3, 4, 5} is not nice because the value 3 cannot be added to any of the other values to have a sum that is divisible by 3. We can easily verify that the subset {1, 2, 4, 5} is a nice set. This is the largest nice subset of values. The sum of its elements is 1 + 2 + 4 + 5 = 12.
{ 1, 2, 3, 4 }
2
Returns: 10
The entire set is nice.
{ 1, 2, 3, 6, 10 }
10
Returns: 0
There's no way to make a pair adding up to something divisible by 10, so in this case the only nice subset of the given values is the empty set. The sum of its elements is zero.
{ 1, 6 }
5
Returns: 0
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }
10
Returns: 210
{1, 9, 19, 29}
10
Returns: 58
The example from the problem statement. This entire set is nice.
{15, 25, 47}
10
Returns: 40
The largest nice subset of this set is {15, 25}.
{5, 1 }
10
Returns: 0
{2, 4, 3, 5, 1 }
3
Returns: 12
{1, 2, 3, 4, 5 }
3
Returns: 12
{3, 6 }
3
Returns: 9
{72, 13, 7 }
79
Returns: 79
{1, 2, 3, 4, 5 }
7
Returns: 14
{1, 2 }
3
Returns: 3
{3, 4 }
3
Returns: 0
{2, 3 }
4
Returns: 0
{3, 5 }
10
Returns: 0
{3, 6, 1 }
10
Returns: 0
{1, 11, 19, 29 }
10
Returns: 60
{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 }
23
Returns: 1275
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }
6
Returns: 210
{15, 25, 47 }
10
Returns: 40
{1, 2, 4 }
2
Returns: 6
{11, 12, 13, 14, 15, 20, 17 }
10
Returns: 30
{23, 25, 27 }
10
Returns: 50
{1, 9, 19, 29 }
10
Returns: 58