GroupingNumbers | Topcoder Archive

Problem Statement

Your are given a int[] numbers. Your task is to split these numbers into exactly n groups such that the difference between the highest average of any group and the lowest average of any group is minimized. Each element of numbers must belong to exactly one of the n groups. Return this minimal difference.

Definition

Class:: GroupingNumbers
Method:: minRange
Parameters:: int[], int
Returns:: double
Method signature:: double minRange(int[] numbers, int n)
(be sure your method is public)

Notes

The return value must be within 1e-9 absolute or relative error of the actual result.

Constraints

numbers will have between 1 and 9 elements inclusive.
Each element in numbers will be between 1 and 1000 inclusive.
n will be between 1 and the number of elements in numbers inclusive.

Examples

```
{1,2,99,100}
```
```
2
```
```
Returns: 0.0
```
The best split is (1,100) and (2,99). Both groups have an average of 50.5, so the difference is 0.
```
{3,3,3,3,3,3,3,3,3}
```
```
4
```
```
Returns: 0.0
```
When all the numbers are the same, the average of any group will be that number.
```
{2,3,5,7,11,13}
```
```
3
```
```
Returns: 0.33333333333333304
```
The best split is (2,5,13), (3,11) and (7). The first group has an average of 6.66..., and the other two groups both have averages of 7. The difference is 0.33...
```
{1, 2, 2, 998, 667}
```
```
2
```
```
Returns: 0.0
```

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.