MedianOfThree

The median of a collection of numbers is the number that is ranked in the middle after the collection is sorted. If the size of the collection is even, then the median is the average of the two middle numbers.

For example:

• median of { 1, 2, 3, 4, 5 } is 3
• median of { 3, 9, 55, 7, 12, 14, 10 } is 10
• median of { 2, 8, 4, 6 } is 5

A 3-number combination is formed by picking any 3 numbers out of a collection. The order is unimportant. Hence, { 1, 2, 3 }, { 2, 1, 3 }, and { 3, 1, 2 } represent the same 3-number combination.

Each number in the collection is considered distinct, even if their values are equal.

For example, { 1, 2, 2, 3 } has four distinct numbers even though two of them are equal to 2.

It may be easier to label them as { a, b, c, d }, with a = 1, b = 2, c = 2, and d = 3. We can then enumerate all the possible 3-number combinations as: { a, b, c }, { a, b, d }, { a, c, d }, { b, c, d }. They are { 1, 2, 2 }, { 1, 2, 3 }, { 1, 2, 3 }, and { 2, 2, 3 }, respectively.

You are given a int[], numbers. Your task is to write a function that calculates the median of each 3-number combination of numbers and returns the sum of these medians.

For example:

{ 1, 2, 3, 4 } has the following 3-number combinations: { 1, 2, 3 }, { 1, 2, 4 }, { 1, 3, 4 }, and { 2, 3, 4 }. Their medians are 2, 2, 3, and 3, respectively. The sum of these medians is 2 + 2 + 3 + 3 = 10.

{ 1, 2, 2, 3 } has the following 3-number combinations: { 1, 2, 2 }, { 1, 2, 3 }, { 1, 2, 3 }, and { 2, 2, 3 }. Their medians are 2, 2, 2, and 2, respectively. The sum of these medians is 2 + 2 + 2 + 2 = 8.