Statistics

Problem Statement for "CreateGroups"

Problem Statement

Your language school is starting a new semester, and each student must select a time schedule. You are given a int[] groups, where the i-th element is the number of students who selected the i-th schedule. Your school has a rule stating that the number of students assigned to each schedule must be between minSize and maxSize, inclusive. However, this rule was not enforced properly during the sign up phase. It is your job to reassign students in such a way that the rule is satisfied. A reassignment is defined as removing a student from one time schedule and placing him in a different time schedule. Return the minimal number of students you must reassign, or return -1 if it is impossible to satisfy the rule. Note that you may not create new schedules or delete existing schedules.

Definition

Class:
CreateGroups
Method:
minChanges
Parameters:
int[], int, int
Returns:
int
Method signature:
int minChanges(int[] groups, int minSize, int maxSize)
(be sure your method is public)

Constraints

  • groups will contain between 1 and 50 elements, inclusive.
  • Each element of groups will be between 1 and 1,000,000, inclusive.
  • maxSize will be between 1 and 1,000,000, inclusive.
  • minSize will be between 1 and maxSize, inclusive.

Examples

  1. {10,20}

    10

    15

    Returns: 5

    We can move 5 students from the second time schedule to the first. Both schedules will then have a size of 15, which is the maximum allowed size.

  2. {20,8,6}

    10

    15

    Returns: 6

    We can move 2 students from the first schedule to the second, and another 4 students from the first schedule to the third. The sizes of the resulting schedules will be 14, 10 and 10.

  3. {10,20,30}

    1

    18

    Returns: -1

    There is no solution possible here. We have 60 students in 3 time schedules, so it is impossible to have at most 18 students per schedule.

  4. {50,10,20,20,5}

    15

    30

    Returns: 20

  5. {100,200,301}

    200

    200

    Returns: -1

  6. {100,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1900,1000,1000,1000}

    1000

    1000

    Returns: 900

  7. {100,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1900,1000,1000,1000}

    1001

    2000

    Returns: -1

  8. {100,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1900,1000,1000,1000}

    999

    1000

    Returns: 900

  9. {100,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1900,1000,1000,1000}

    998

    999

    Returns: -1

  10. {1000000}

    1000000

    1000000

    Returns: 0

  11. {999999}

    1000000

    1000000

    Returns: -1

  12. {999999}

    999997

    999998

    Returns: -1

  13. {353802}

    353798

    353803

    Returns: 0

  14. {153183,944413,546962,393535}

    509520

    509521

    Returns: -1

  15. {23280,803789,309145,345215,23120,311585,947808,650,987948,694343,990901,42861,632341,507689,166254,287046,256156,361030,438632,103757,782736,577932,75180,783591,838709,104447,422775,88467,360196,839298,196815,449609,255598,943640}

    439778

    439778

    Returns: -1

  16. {854699,305579,732612,336885,435990,582239,725063,758521,211809,918019,787945,973136,371398,600785,948416,261059,273576,883953}

    608977

    608983

    Returns: 2101517

  17. {906208,547842,471448,351,510012,204189,559952,148761,484868,915,779478,787629,987388,492,511367,743152,307942,211401,945940,515356,781049,166057,542619,427976,475,912433,859,692197,869760,159543,236,671238,628341,990137,552426,971936,916991,202130,673229}

    507286

    507292

    Returns: 5328964

  18. {609442}

    609439

    609444

    Returns: 0

  19. {839593,966231,661,525751,875501,145354,662155,819596,233864,277585,814,378374,658318,96,553585,467,833507,602737,357721,597977,462049,543,543322,77407,446,896655,550478,419,790478,808994,871685}

    462334

    462337

    Returns: 4536876

  20. {463751,683909,770,251062,834026,851,754289,91358,967035,316705,89881,526182,153935,579082,406489,505,556642,424012,901311,322121,514959,860984,277631,618703,118154,424944,667557,434182,617084,499033,783239,627158,632252,307136,499,628008,273098,280742,429044,786448,547724,328474,401218,257123,408797}

    445509

    445516

    Returns: 4693540

  21. {890340,540028,310,616161,247506,534590,805995,880564,858590,833781,167106,525,63247,556970,726789,508193,29697,525083,290243,552707,347,239964,633054,932435}

    476424

    476428

    Returns: 3248871

  22. {346876,481443,430260,440463,601915,909290,479,981549,782430,70629,913221,668052,556481,133359,599469,691351,193905,995077,455373,860562,604262,825515,359,807083}

    556222

    556223

    Returns: -1

  23. {437111,609498,254430,193558,841921,865137,881633,705664,500,850206,670474,90088,829390,389134,213744,426816,285781,858013,643335,131842,830377,937568,872081,878980,422761,615,460093,299775,801633,300039,596032,20560,433804,704543,419673,31}

    504351

    504356

    Returns: -1

  24. {488687,926018,649745,196493,532540,574686,23826,185335,337963,920838,284,400381,555097,495207,145779,278519,908510,581041,440798,923254,60,31632,617129,683263,330509,965583,466020,652737,726236,18294,571489,49837,346454,540773,913241,995983,584245,918171,815338,372253,622616,765622,508407}

    513040

    513041

    Returns: -1

  25. {89918,527920,704682,680930,963,502612,959600,777,537680,891817,644800,162948,575576,745311,990643,267}

    501024

    501030

    Returns: 2250247

  26. {26368,158658,773537,735420,773026,329458,230082,930546,152463,89526,404356,156720,757467,70744,337097,150,362908,96941,345022,897092,484328,252032,572379,491932,87653,103518}

    369976

    369976

    Returns: -1

  27. {753062}

    753060

    753063

    Returns: 0

  28. {303099,88619,852,377003,105155,254296,294596,152852,706450,945507,643030,316673,872,553095,995302,935743,228630,681877,725592,693143,160775,352185,957805,452813}

    455245

    455249

    Returns: 3285054

  29. {98582,237083,860660,197137,328460,320436,62349,170863,201065,761998,688005,632355,63846,953251,281203,408179,11678,264903,495717,893304,299536,44406,955,580635,492525,936467,548905,533562,920,290,53428,230610,235962,705109}

    370422

    370423

    Returns: -1

  30. {221,578001,700715,5768,54961,219608,271,912452,528331,466109,929321}

    399615

    399616

    Returns: -1

  31. {465,43545,320893,392697,258476,531261,2745,425003,160703,422617,66214,378662,963835,723,228170,356673,553233,371873,255691,77391,353352,271542,686061,260,64,594413,590477,564646,172587,155637,332114,200890,445869,622730,437991,911885,984237,565740,697194,58413}

    361425

    361425

    Returns: -1

  32. {258253,923519,807351,747152,178934,906858,510667,371673,374558,954517,688794,780128,241655,569,187948,952421,343,139275,61036,682005,545769,304131,192741,335003,771123,135072,464892,832562,177411,720095,628696,133214,761843,844212,584121,997132,488829,318104,849146,977688}

    520736

    520739

    Returns: 5540412

  33. {660771,503042,129736,512030,942772,793972,293437,468277,632999,314003,751292,321,158089,34448,680366,450335,618338,672229,153029,156588,362640,35258,229546,721538,890495,560946,180452,473,704765,720617,967,678195,221524,349092,273,517,679605,109707,765294,297786,35963,610240,447630,242740,4}

    394937

    394940

    Returns: -1

  34. {371260,334308,879448,938198,333848,167147,945135,273694,787376,238113,856145,27579,862,71226,688039,962154,709370,880,584992,33360,149828,868689,24326,136,297383,211596,943,679003,618526,425854,776614,539161,748923,516,626531,144574,806358,266944,951,949914,817838,227323,881,490321,264499,626092,770024}

    436955

    436955

    Returns: -1

  35. {705257,988304,694896,991667,42506,632668,507418,165977,286927,256092,360885,438586,103605,783131,578291,75291,783235,838351,104321,422863,88768,360628,838798,196795,450117,256402,943694,937446,959737,541832,175295,920779,46339,802511,324857,296013,457,23043,854140,305711,732083,336989,436417,582371,724844,758418,211853}

    486521

    486525

    Returns: 6396321

  36. {42978,122878,276300,515604,142527,157859,213269,423926,906240,548337,471225,246,510665,204140,560839,148552,485123,489,779255,787001,987486,351,511333,743287,307117,211229,945632,515719,781599,166685,543087,428060,228,912677,860,692738,870163,159857,438,670673,627798}

    423766

    423770

    Returns: 5471785

  37. {476701,913671,658097,732647,923273,526212,875902,144409,661708,819499,233284,277362,469,377777,659101,132,553540,931,834356,603291,358291,597456,461872,982,543285,78296,960,896672,551112,669,789781,808677,872263,98622,510089,626110,645867,685,582237,681122,542930,320729,821950,16718}

    479084

    479087

    Returns: 5774623

  38. {424097,671178,884360,576943,785,405943,843,556897,423579,900746,322667,515608,860998,277927,618537,118456,424913,667784,433643,616549,498638,783698,627176,632098,306745,747,628340,272819,280489,428842,786933,548188,328590,401560,256536,408076,364,76521,867335,492083,120683}

    449971

    449973

    Returns: -1

  39. {399257,627,290381,552664,615,239406,632265,931877,463096,213845,961738,448830,810205,798309,799646,553,765197,958555,29021,195448,948141,188241,346469,480650,430254,440767,602289,909310,313,981678,782330,70513,913004,668042,556434,133220,599641,692295,193706,995277,455495,861046,604201,825455,988,807701}

    521279

    521281

    Returns: -1

  40. {126716,976667,670265,553194,849502,671106,89995,829898,389073,213837,426838,286168,858200,643651,131949,829677,937197,871839,878849,422517,806,460438,299298,801015,300076,595841,20267,433750,704554,419874,806,492094,860355,430362,770988,525203,405328,575,743199,297424,417834,254,544,743789,226337}

    480177

    480185

    Returns: 5723198

  41. {654625,423739,205,441179,922983,899,31596,617722,682617,330586,965410,466050,653216,725323,18699,571314,49675,346086,540617,913236,996056,584804,917945,815662,372152,622064,766074,508404,977725,211759,6299,800616,109417,895062,587269,812661,804828,345361,721,527296,704395,680265,699,503306,959493,899,538241,890892}

    526998

    527001

    Returns: -1

  42. {211313,79260,710012,316522,74705,38849,831576,525619,450234,374444,169000,176816,362568,96850,345236,896702,484162,252205,572336,492012,86860,103369,666979,270,483554,815869,921323,98417,248893,640,410890,400926,935470,651265,578,224747,977,237170,567218,495001,967449,86129,119400,377296}

    371838

    371841

    Returns: -1

  43. {723188,49623,419065,880699,426851,906819,413,590720,948960,122687,171,841032,640887,495420,49939,627284,321017,98698,236460,861191,197165,327706,320937,62728,170055,200753,761568,688509,632473,63597,953205,281736,408198,12232,264690,495022,893858,299799,45139,199,581509}

    412246

    412248

    Returns: -1

  44. {574924,768059,675023,642,507418,508926,470362,92361,95971,947077,796784,481451,452968,898078,745621,483847,305701,810115,465020,764725,264126,486467,35842,43441,320833,393032,258628,531741,2501,424997,160565,422701,66479,378553,963536,155,228269,356469,552822,372323,255659,77410,353138,271851,686585,588,280,594089}

    403085

    403087

    Returns: 5339248

  45. {470276,66922,307516,313,241134,78649,465967,646737,783840,297834,959610,946718,950630,258148,923124,806768,746909,179443,907463,511219,371992,374916,954671,689220,780501,241033,92,187922,952807,567,139514,61411,681792,545767,303665,192135,335014,770796,134940,465134,833099,177175,719639}

    475883

    475885

    Returns: 6069495

  46. {991497,871088,690977,141252,40146,297203,325823,647083,660543,503046,129562,512391,942135,794346,293717,468565,632614,313543,751325,495,158228,34893,680461,450440,618354,671953,153570,156536,363068,35741,229761,721716,891109,560946,180513,19,704539,720227,99,678093,220786,349050,180,143,679585,108893,765560,297381,36041}

    417859

    417865

    Returns: 6579833

  47. {676313,454828,602662,371255,334158,879621,938470,334281,167666,945380,273302,787397,238235,856559,28108,362,70967,687095,961981,710143,603,585353,32779,149623,868644,24318,942,296968,212358,629,678268,618238,425853,777090,539220,749419,164,626510,145151,806526,267169,488,949455,817537,227274,951,490520,264839}

    434904

    434907

    Returns: -1

  48. {881917,533537,815987,199541,764922,525735,432180,45083,886639,484707,268,793147,377383,293,512,495988,117058,837323,861134,938980,602405,896,199,389275,607906,229125,359630,748037,504,542674,900088,362030,105468,399113,154952,661376,826855,526055,364108,446148,13,918942}

    455668

    455669

    Returns: -1

  49. {603143,516493,432492,612141,762129,513106,855563,269330,300095,878233,956062,874835,43659,140,93070,357427,780240,297265,685763,521631,665092,897754,652402,529758,36683,349420,849037,901370,504088,839475,191,196851,396877,674812,136967,828095,608872,695,143,276586,399108,924845,96479,509127,487456}

    491443

    491446

    Returns: 5657926

  50. {266,317903,371257,39138,82604,469957,243270,807185,537,128,84807,426861,921672,333431,571689,92892,790196,825001,755264,658436,9,108003,278,114766,925366,180064,377493,129627,638823,185486,368,756407,344133,864319,916750,989818,730635,675,838726,632,319729,209}

    386061

    386064

    Returns: -1

  51. {728066,600547,130019,144189,927576,152347,121123,349374,894606,445657,754368,347378,285624,726125,319327,542302,819278,355437,540999,863820,362107,130832,468,846115,657752,672228,977248,877555,283770,92539,763834,492012,906875,797,223589,133607,378721,836501,344737,722512,660,313218}

    477754

    477757

    Returns: -1

  52. {94,569441,747921,62807,145,755130,718019,37495,589,329182,354818,186094,807128,973968,180762,287545,330,468599,245501,835,233679,448319,357081,68937,887875,908948,842013,594858,174297,228680,577347,443894,369474,497,722252,871137,963409,637892,462716,384175,743249,269594,955718,289439,440739}

    435612

    435616

    Returns: 5957026

  53. {912172,208826,90753,281740,778009,34339,437295,957398,948890,466342,356160,243599,364964,740271,886197,920243,267662,841845,170877,309081,338844,359,775656,421408,228170,693637,234528,256697,508045,581870,390478,981623,771450,399511,14526,171383,228004,159334,160104,597109,551,291556,60092}

    429801

    429805

    Returns: 5491367

  54. {892010,751683,709596,932845,128115,112771,810541,947314,612115,625871,185273,58583,36739,252955,196609,542444,162254,405337,887621,769662,422791,312152,102871,141331,579630,296593,409637,271571,485486,884482,397444,502791,90055,797810,612348,462,401167,39239,919102,508775,245107,663055,420101,436,234059,538181,650403,280809,228637}

    437893

    437895

    Returns: -1

  55. {1,10,10}

    9

    20

    Returns: -1

  56. {1,1,1,1,1,2}

    1

    2

    Returns: 0

  57. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    500000

    500001

    Returns: 12499975

  58. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    500000

    500000

    Returns: -1

  59. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    500001

    500001

    Returns: -1

  60. {55,33,45,71,27,89,16,14,61}

    33

    56

    Returns: 53

  61. {49,60,36,34,36,52,60,43,52,59}

    45

    51

    Returns: 31

  62. {5,5,5,5,5}

    5

    5

    Returns: 0

  63. {100, 200, 301 }

    200

    200

    Returns: -1

  64. {10, 20, 30 }

    1

    18

    Returns: -1

  65. {55, 33, 45, 71, 27, 89, 16, 14, 61 }

    33

    56

    Returns: 53

  66. {20, 8, 6 }

    10

    15

    Returns: 6

  67. {55, 33, 45, 71, 27, 98, 16, 14, 61 }

    33

    56

    Returns: 62

  68. {4, 6, 2 }

    5

    10

    Returns: -1

  69. {15, 25 }

    20

    20

    Returns: 5

  70. {1, 2, 3, 4, 5, 6, 7, 8, 9 }

    4

    5

    Returns: 10

  71. {3, 7, 7 }

    4

    8

    Returns: 1

  72. {49, 60, 36, 34, 36, 52, 60, 43, 52, 59 }

    45

    51

    Returns: 31

  73. {2, 2 }

    1

    1

    Returns: -1

  74. {5, 2 }

    3

    5

    Returns: 1

  75. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    500000

    500005

    Returns: 12499975

  76. {16, 16, 12 }

    10

    15

    Returns: 2

  77. {123412, 123141, 125343, 274567, 155132, 342345, 123125, 345345, 231234, 163454 }

    123456

    300000

    Returns: 87690

  78. {16, 15, 15 }

    10

    15

    Returns: -1

  79. {10, 10, 10, 10, 11 }

    1

    10

    Returns: -1

  80. {100, 200, 299 }

    200

    200

    Returns: -1

  81. {9, 10, 11, 14 }

    10

    11

    Returns: 3

  82. {1, 10, 10, 10 }

    9

    10

    Returns: -1

  83. {2, 4 }

    3

    3

    Returns: 1

  84. {30, 41 }

    10

    35

    Returns: -1

  85. {3, 4, 1, 1, 1 }

    2

    5

    Returns: 3

  86. {2, 3, 4, 5, 6, 7 }

    4

    5

    Returns: 3

  87. {4, 4 }

    4

    4

    Returns: 0

  88. {1, 2, 4 }

    1

    2

    Returns: -1

  89. {1, 10 }

    2

    10

    Returns: 1

  90. {20, 21 }

    10

    20

    Returns: -1

  91. {5, 5, 5, 6 }

    5

    5

    Returns: -1

  92. {999999, 999999, 999999, 999999, 999999, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 1, 1, 1, 1, 1 }

    500000

    500000

    Returns: 12499975

  93. {999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    500000

    500000

    Returns: 12499975

  94. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    499000

    501000

    Returns: 12475000

  95. {10, 110 }

    20

    100

    Returns: 10

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: