TopCoder Statistics - Problem Statement

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...
{2,3,5,7,11,13,17,19,23}

6

Returns: 6.0
{2,3,7,7,11,13}

3

Returns: 0.25
{1, 2, 2, 998, 667}

2

Returns: 0.0
{2,3,5,7,11,13,17,19,23}

5

Returns: 2.333333333333334

worst case
{65,43,455}

3

Returns: 412.0
{769,197,410,883,93}

5

Returns: 790.0
{367,33}

1

Returns: 0.0
{786,706,500,781,76}

2

Returns: 55.33333333333337
{710,241,327,802,288,528,533}

7

Returns: 561.0
{110,438,333,276,989,14}

4

Returns: 162.0
{933,240,513,830}

2

Returns: 85.0
{812,224,264,702,724,51}

3

Returns: 51.5
{625,374,648,552,313,854,686,899}

6

Returns: 134.0
{242,26,303,443,310,670,981,246,710}

3

Returns: 7.399999999999977
{242,26,303,443,310,670,981,246,710}

9

Returns: 955.0
{242,26,303,443,310,670,981,246,710}

1

Returns: 0.0
{21,461,239,952,149,933,370}

4

Returns: 107.0
{746,716,516,508,776,184,434,511}

4

Returns: 51.66666666666663
{31,724,688,968,145,323,964,395}

6

Returns: 401.0
{143,478,777,973,265}

3

Returns: 80.0
{308,154,934,746}

3

Returns: 438.0
{825}

1

Returns: 0.0
{493,584,880,585,564,540,559,596,464}

1

Returns: 0.0
{509,489,390,875,369,245,42}

7

Returns: 833.0
{548,151,443,85}

2

Returns: 19.5
{59,679,306,607,41,461,311}

6

Returns: 548.0
{698,75,492,156,57,953,668,414}

5

Returns: 118.5
{2, 3, 5, 7, 11, 13 }

3

Returns: 0.33333333333333304
{1000, 1, 3, 4, 5, 6, 8, 12, 12 }

4

Returns: 161.83333333333334
{1, 4, 6, 7, 3, 2, 99, 108, 106 }

3

Returns: 0.0
{9, 9, 8, 8, 7, 7, 6, 345, 54 }

8

Returns: 168.5
{1, 2, 3, 4, 5, 6, 7, 8, 9 }

7

Returns: 4.0
{1, 2, 3, 4, 5, 6, 7, 8, 9 }

8

Returns: 6.0
{45, 34, 67, 89, 65, 41, 21, 101, 48 }

7

Returns: 26.0
{1, 2, 3, 4, 5, 6, 7, 8, 9 }

4

Returns: 0.0
{1, 10, 100, 1000, 500, 50, 5, 30, 300 }

9

Returns: 999.0
{1 }

1

Returns: 0.0
{1, 2, 2, 998, 343, 1, 34, 2, 4 }

3

Returns: 138.0
{1, 1, 1, 1, 1, 9, 99 }

3

Returns: 19.6
{1, 2, 99, 23, 29, 101, 103, 87, 187 }

8

Returns: 101.0
{101, 102, 103, 1, 2, 2 }

6

Returns: 102.0
{100, 101, 311, 718, 165, 173, 177, 871, 653 }

9

Returns: 771.0
{13, 425, 123, 664, 745, 342, 999, 756, 34 }

5

Returns: 111.0
{11, 345, 322, 355, 355, 332, 666, 333, 222 }

6

Returns: 34.333333333333314
{3, 3, 3, 2 }

2

Returns: 0.3333333333333335
{1, 513, 235, 123, 21, 323, 12, 33, 22 }

3

Returns: 15.0

Statistics

Problem Statement for "GroupingNumbers"

Problem Statement

Definition

Notes

Constraints

Examples