MedianProcess | Topcoder Archive

Problem Statement

We wish to assign a score to the given array values. An empty array is assigned the score 0. Otherwise, we have one of the following cases:

The array has an odd number of elements: Compute the median m, remove one copy of m from the array, and then compute the score s of the new smaller array. The resulting score is s + m.
The array has an even number of elements: Find the maximum element m, remove one copy of m from the array, and then compute the score s of the new smaller array. The resulting score is s - m.

Return the score of values.

Definition

Class:: MedianProcess
Method:: getScore
Parameters:: int[]
Returns:: int
Method signature:: int getScore(int[] values)
(be sure your method is public)

Notes

Given K numbers, their median is the ((K+1)/2)-th smallest of them, rounding down for even K, and indexing from 1. For example, the median of (1, 2, 2, 3, 5) is 2, and the median of (11, 13, 12, 14, 15) is 13.

Constraints

values will contain between 0 and 50 elements, inclusive.
Each element of values will be between -1000 and 1000, inclusive.

Examples

```
{}
```
```
Returns: 0
```
The array is empty, so we return 0.
```
{2}
```
```
Returns: 2
```
We remove the median 2 and obtain an empty array. Thus the return value is 2.
```
{2,3}
```
```
Returns: -1
```
We first remove the max 3, and later the median 2. Thus the result is -1.
```
{1,1,1,1}
```
```
Returns: 0
```

{371,-56,933,519,583,520,938,-398,75,-269,895,-790,982,-941,937,888,-416,-360,714,-594,-783,431,595}

Returns: -12234

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.