Statistics

Problem Statement for "MedianProcess"

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

  1. {}

    Returns: 0

    The array is empty, so we return 0.

  2. {2}

    Returns: 2

    We remove the median 2 and obtain an empty array. Thus the return value is 2.

  3. {2,3}

    Returns: -1

    We first remove the max 3, and later the median 2. Thus the result is -1.

  4. {1,1,1,1}

    Returns: 0

  5. {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

  6. {-367,898,854,255,774,556,719,-206,-866,-100,405,82,-336,474,60,-657,-460,153,-44,776,-3,-968,155,679,914,-206,-557,-532,-122,-127,308}

    Returns: -13493

  7. {-973,-714,-551,276,-836,-360}

    Returns: -1888

  8. {-186,-694,460,870,-636,-822,756,-99,-131,-56}

    Returns: -4400

  9. {416,-938,926,672,-804,550,-997,-905,-118,-659,915,-39,-587,-200,828,-864,-368,-649,114,142,-549,642,-415,520,-746,323,148,633,993,138,245,264,814,-425,-709,679,23,998}

    Returns: -20681

  10. {-685,663,-137,-679,674,46,383,372,609,250,879,814,-252,-286,889,936,-476,873,107,952,984}

    Returns: -9630

  11. {-775,-153,351,-186,820,399,187,-948,596,-885,931,-180,-526,334,542,-424,-705,870,74,353,-750,-799,75,-303,508,-540,906}

    Returns: -13972

  12. {-993,-761,-702,238,856,-427,-228,475,-596,-608,899,-532,-342,-821}

    Returns: -6484

  13. {-827,439,-375,-110,-944,-557,635,922,-296,-818,257,-937,4,709,-249,30,370,940,360,-824,-261,442,-838,637,-979,-377,-207,-294,64,390,804,442,-775,-432,-46,594,183,-376,825,879,-202,-425,812,-159,-548,364}

    Returns: -22866

  14. {629,604,413,287,334,-903,611,-748,-254,101,-437,560,-182,573,-444,-781,535,556,-565,360,337,750,305,-321,-173,-614,-151,837,105,641,915,143,-258,-431,-1,-958,-891,857,-757,-137,636,568,-309,-370}

    Returns: -21140

  15. {-510,-370,740,303,-288,100,-171,-643,601,-88,-753,107,484,794,-752,3,43,-217,-848,-843,660,299,613,-550,-221,0,-611,161,-266,-42,-29,655,405,455,-121}

    Returns: -13746

  16. {-401,-669}

    Returns: -268

  17. {-304,87,-397,636,-653,897,-82,201,503,581,274}

    Returns: -4039

  18. {-651,16,426,-614,432,-457,-637,79,-451,146,-615,127,537,839,-594,952,634,374,-679,-848,956,-976,563,-261}

    Returns: -12832

  19. {-768,-717,-107,275,701,-5,-432,-82,-335,963,-937,251,-41,162,29,-36,854,169,-727}

    Returns: -7581

  20. {-434,43,197,-365,844,-87,770,554,138,-221,-528,-8,417,-135,-139,-936,-37,-250,99,531}

    Returns: -6717

  21. {-559,89,729,666}

    Returns: -1865

  22. {-335,576,-829,271,757,-371,446,-728,381,-938,350,317,-179,467,-965}

    Returns: -7368

  23. {514,-622,-277,386,777,-428,-888,958,-269,362,-270,305,-423,311,-656,-155,724,-875,948,514,153,833,758,-999,-88,-212,-836,-664,-375,488,643,145,540}

    Returns: -17106

  24. {-728,670,755,-170,666,-442,11,27,915,-609,-274,-425,412,940,-247,980,-661,180,-190,402,26,299,449,784,-618,77,-6,-23,173,-657,-40,42,-935,-518,140,78,-10,414,-260,27,-286,891,750,-774,237,463}

    Returns: -18553

  25. {712,68,-894,-102,664,-648,56,-982,-184,314,-816,400,110,576,-46,151,-525,492,875,815,143,877,232,-680,-312,223,824}

    Returns: -11967

  26. {605,840,-505,326,148,-801,275,-41,910,-757,141,618,627,381,549,-343,641,493,234,201,501,355,-959,-6,-688,-368,957,-376,595,-217,-987,-605,684}

    Returns: -15286

  27. {-835,-650,947,-602,920,954,-481,-57,-944,-664,635,-497,-463,82,-860,712,-551,135,308,-618,-352,523,710,-353,-311,-645,542}

    Returns: -14615

  28. {-454,824,-425,447,-312,-225,-347,708,109,-183,583,264,99,-45,-886}

    Returns: -5911

  29. {-293,183,756,-875,-857,661,-805,-758,-306,-318,181,485,-912,907,-39,-27,-244,99,523,98,-108,-48,-730,-190,852}

    Returns: -11123

  30. {-960,915,20,68,-109,-55,28,-176,464,181,937,-600,381,72,-154,478,-340,-542,283,725,865,-225,-317,858,420,730,-744,456,-683,-205,688,-492,293,330,181,691,525,-856}

    Returns: -16671

  31. {-99,-183,843,802,-375,330,486,-710,-551,-947,-292,283,168,289,755,53,798,797,-299,441,-930,400,430,786,-16,343,-996,211,-633,12,-565,912,514,197,-961,-153,-503,-443,95,-925,957}

    Returns: -20163

  32. {785,-121,873,230,101,745,94,-673,750,325,267,-726,926,-463,220,413,314,167,-213,960,-368,471,-353,574,622,-400,-200,-57,525,-39,-6,-188,-269,56,609,82,-401,-240,327,-167,-793}

    Returns: -15649

  33. {-797,403,-795,653,727,77,-140,-809,-106,285,902,120,334}

    Returns: -5754

  34. {823,-209,181,554,935,758,-525,730,657,903,-354,-418,-728,691,-93,784,-308,468,196}

    Returns: -8625

  35. {-335,-240,-225,885,-715,669,495,399,663,-288,338,-892,204,638,-117,-45,32,-818,39,-76,823,-982,-389,239,-471,701}

    Returns: -11718

  36. {299,324,-140,-278,745,-545,-506,-552,489,611,-112,380,902,974,331,324,-121,-882,-371,979,-982,596,-807,351,798}

    Returns: -12153

  37. {-583,851,-711,-198,986}

    Returns: -3329

  38. {-348,-573,-224,-109,535,-766,-900,186,-726,-932,194,-78,768,-573,-973,530,880,659,802,116,243,487,840,-106,497,-350,-57,297,118,-309,-251,-875,-733,730,-831,440,364,445,523,-156,-517,422,-345,-804,-964,542,26,-55}

    Returns: -23089

  39. {120,531,744,-428,168,614,272,-730,302,171,-178,-784,609,-332,566,-774,-921,-91,-780,228,-921,-993,-774,840,809,209,588,0,-343,453,-22,802,949,-188,-143,699,727,287,-990,350,-161,825,-898,-397,-81}

    Returns: -22552

  40. {2, 2, 2 }

    Returns: 2

  41. {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

  42. {8, 7, 46, 4, 78, 5, 75, 4, 4, 4, 4, 4, 4, 4, 465, 4, 56, 5, 56, 5, 90, 90, 56 }

    Returns: -976

  43. {3, 2 }

    Returns: -1

  44. {-2, -3 }

    Returns: -1

  45. {1, 3, 5, 7 }

    Returns: -8

  46. {1, 1, 1, 1 }

    Returns: 0

  47. {1, 500, 50 }

    Returns: -449

  48. {-100 }

    Returns: -100

  49. {3, 1, 2 }

    Returns: 0

  50. {1, 110, 5 }

    Returns: -104

  51. {1, 110, 111 }

    Returns: 0

  52. {-1, -2, -3, -4 }

    Returns: -4

  53. {6, -5, 78, 4, 7, 7, 5, 7, 5, 45, -5, 76, 6, -3, 605, 5, -5, -4, -6, -43, 6, 3, 457, 56, 3, 56, 4 }

    Returns: -1454

  54. {371, -56, 933, 519, 583, 520, 938, -398, 75, -269, 895, -790, 982, -941, 937, 888, -416, -360, 714, -594, -783, 431, 595, 123, 148, 124, 785, 648, 354, -457, -78, 24, -789 }

    Returns: -16530

  55. {5, 3, 6, 8, 11, 22, 34, 12, 54, 32, 32, 33 }

    Returns: -162

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.
This problem was used for: