Statistics

Problem Statement for "Necklaces"

Problem Statement

A group of n thieves needs some software to help them divide up their loot. A necklace must be divided up as evenly as possible among the gang members. The necklace is a circle of gems of different values.

The requirement is that the necklace be divided into n segments by cutting the necklace in n places. Every segment must contain at least one gem. The "inequity" of the division is the value of the most-valuable segment minus the value of the least-valuable segment. (The value of a segment is the sum of the values of the gems in that segment.) We want to minimize the inequity.

Create a class Necklaces that contains a method inequity that is given as input n and a int[] gems (the values of each gem in the necklace in order). The gems are in a circle, so the last element of gems is connected to the first element. The method should find the best way to divide the necklace and return the minimum possible inequity.

Definition

Class:
Necklaces
Method:
inequity
Parameters:
int, int[]
Returns:
int
Method signature:
int inequity(int n, int[] gems)
(be sure your method is public)

Constraints

  • n will be between 1 and 50 inclusive.
  • gems will contain between n and 50 elements inclusive.
  • Each element of gems will be between 1 and 100,000 inclusive.

Examples

  1. 1

    {5,12,2,9}

    Returns: 0

    Cut it once anywhere. There is only one segment, and its value if 28. The difference between the worst and best segment is 0 (28 - 28).

  2. 2

    {5,12,9,2}

    Returns: 4

    Cut it between the 5 and 12, and also between the 12 and 9. The two resulting segments have values 12 and 9+2+5=16.

  3. 4

    {100,92,133,201,34,34,34,94,108}

    Returns: 29

    Divide it as follows: 108 100 | 92 133 | 201 | 34 34 34 94. Then the result is 225 - 196.

  4. 4

    {100,107,103,109,103,102,110,140,190,130,120,200, 300,109,108,107,106,155,144,103,108,300,400,130, 120,140,230,150,110,107,102,100,100,100,100,100, 100,100,100,100,100,100,100,100,100,100,100,100,100,100}

    Returns: 25

  5. 5

    {100,107,103,109,103,102,110,140,190,130,120,200, 300,109,108,107,106,155,144,103,108,300,400,130, 120,140,230,150,110,107,102,100,100,100,100,100, 100,100,100,100,100,100,100,100,100,100,100,100,100,100}

    Returns: 52

  6. 4

    {90,1,100,1,90,1,1,1,1,1,1,1,1,1}

    Returns: 91

  7. 2

    {1,1,1,1,1,1,6,1,1}

    Returns: 0

  8. 3

    {1,1,1,1,1,1,6,1,1,1}

    Returns: 2

  9. 3

    {1010,912,1,812,922,922,6,34,811,11,123,234,345,456,345,345,234,5467,345,234,456,234,234,1,4,32,5,32}

    Returns: 1155

  10. 4

    {1010,912,1,812,922,922,6,34,811,11,123,234,345,456,345,345,234,5467,345,234,456,234,234,1,4,32,5,32}

    Returns: 2770

  11. 5

    {1010,912,1,812,922,922,6,34,811,11,123,234,345,456,345,345,234,5467,345,234,456,234,234,1,4,32,5,32}

    Returns: 3560

  12. 20

    {1010,912,1,812,922,922,6,34,811,11,123,234,345,456,345,345,234,5467,345,234,456,234,234,1,4,32,5,32}

    Returns: 5393

  13. 4

    {50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,49,1000,345,23,23}

    Returns: 595

  14. 7

    {50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,49,1000,345,23,23}

    Returns: 825

  15. 1

    {6}

    Returns: 0

  16. 2

    {1,100000}

    Returns: 99999

  17. 27

    {86261,26865,88477,46270,4895,88972,8701,25981,60377,37943,21831,61223,99331,30094,98178,41214,37295,43332,44932,68243,71617,5340,58306,41235,10774,5640,46021,34257,52864,49340,91710,97548,95055,56109,67856,48220,67820,30891,57387,6079}

    Returns: 72676

  18. 7

    {67033,1914,92336,1316,15281,81870,71786,73639,84138,47641,47675,93017,79401,79526,39417,35474,15675,22066,16639,24537,79838,24476,55732,23947,84953,31880,87852,41995,60588,24527,73160,80288,24419,18951,21529,49103,68,86795,23810,29397,75047,65191,10907,30753,29509,81858,38066,75469,97449,11431}

    Returns: 43751

  19. 48

    {5284,66738,36713,80704,24061,45204,26949,72608,73957,12931,20506,90915,23175,32930,57283,35460,18398,45672,39228,58085,12482,46607,28741,98984,64346,34907,49509,84909,66037,15748,92427,95689,1588,38050,99728,25887,28799,10773,62680,64829,13559,20974,45048,38070,31531,29918,78865,22743,54501}

    Returns: 94444

  20. 41

    {39433,62940,65765,40060,16514,66860,44229,44406,54855,37826,42045,22145,87714,74609,45537,65486,86972,65475,33278,83692,7960,7209,39589,39878,70508,93235,9775,67304,36124,36315,84658,44770,45429,57595,68895,14245,39875,17087,69396,51434,18159,22037,68229,66194,312,11297}

    Returns: 78066

  21. 16

    {43564,66701,1348,84259,4356,51006,45466,3783,28250,79745,69611,16459,82951,95844,31591,13782,42397,87394,51439,16707,9438,21782,33149,40579,91416,58481,64752,59457,20157,16390,5336,78304,29955,27906,31195,67073,11444}

    Returns: 48590

  22. 23

    {5249,22707,14427,89988,16703,3532,50374,6636,86811,85782,87381,40105,13306,91657,92822,11794,64934,54198,96346,67924,22899,31559,645,23961,19548,1299,98565,84471,39467,41342,88767,78578,92215,28779,59620,58159,75048,95167,2339,22934,81910,53236,37593,78530,99503,86294,18083,95849}

    Returns: 65243

  23. 6

    {92308,81283,70507,4040,80642,71897,48766,43602,95514,78891,87044,87572,25332,19453,95085,92375,10305}

    Returns: 51724

  24. 27

    {38676,39936,44856,90890,90538,38705,36366,1094,11546,52161,99221,3643,40514,69795,63218,25166,62133,99296,73514,99212,98260,60037,24012,9937,11275,94011,17687,10087,17194,19828,6953,97190,59806,78401,13030}

    Returns: 78084

  25. 8

    {55201,1857,30498,5097,28499,40522,4629,80025,61100,40756,41887,21346,72420,79073,70057,30412,37035,98829,98102,85335,29722,27988,57641,52473,79395,2849,52740,60435,14602,69556,17484,68814,96813,1614,85704,35767,42303,54684,68168,61077,10642,9598,7267,39043,37746,25139,12312,26318,30671,21827}

    Returns: 34720

  26. 12

    {24083,41288,90263,74455,45970,19834,69799,21125,56894,81846,13954,52517,2074,85642,68283,96504,73095,76703,82490,29322,62970,45860,79005,29612,99182,95347,83231,38319,98454}

    Returns: 67820

  27. 2

    {52766,16587,86824}

    Returns: 17471

  28. 37

    {93123,1609,62002,87945,19235,50304,95458,83877,78379,37673,62304,11744,78063,22984,44685,35341,77319,34873,3538,81968,40828,88757,33024,73282,74626,29181,59161,16481,87205,51782,583,14417,57468,63298,37577,79699,21371,14631,73007,24321,9572,3582,30427,5987,55869,26570,65447,75473,77852,46290}

    Returns: 66277

  29. 5

    {50687,86669,29249,59451,62809,62633,41827,42281,14279,29528,60625,47125,93568,45560,1009}

    Returns: 13192

  30. 2

    {9374,22636,15053,20042,77822,21839,70389,99475,90105,90794,18986,12224,26243,98651,52542,97788,61615,11621,97039,39710,59898,40025,73449,21267,48913,61911,64089,8084,58560,89262,41226,50166,50808,67743}

    Returns: 1807

  31. 9

    {24284,33856,92457,54038,88905,40476,18125,80404,52159,56791,47950,37239,17520,2736,63314,66454,85667,90399,41655,85006}

    Returns: 57276

  32. 7

    {40784,65914,4782,15203,18589,40321,93195,37291,72327,35978,69645,96051,49173,61930,42702,24992,8269,71838,88283,99742,29130,66804,72034,98278,72502,7204,10905,29560,46693,98236,26952,22632,16687,28408,79125}

    Returns: 58350

  33. 39

    {47761,63531,56180,64796,50924,2213,11819,63211,80115,73980,1306,70847,54625,69259,72020,82471,46007,88283,45834,88306,4460,76592,21961,53897,97409,11663,37306,98248,45329,64202,86247,74619,49479,32970,64318,67378,48267,74072,57069,6241,17365,80264,19757,19062,9506}

    Returns: 84216

  34. 2

    {48759,50403,95950,21442,91223,81778,33563,83093,91285,93824,28332,36760,88306,15370,50081,1822,67309,79754,83101,86093,86812,16522,23193,81629,65321,45715,62180,95199,99206,63043,70645,86298,62703,70141,12719,60145,16731,84923}

    Returns: 3527

  35. 43

    {84510,17214,23381,1798,52926,12998,69357,93661,74384,11261,76185,59364,35407,20877,20861,38846,70840,29874,65478,51091,47492,49258,51831,15028,74659,43689,7890,51579,97330,83145,94144,85552,20472,99135,46173,63913,61859,83849,20195,26729,24730,46051,20241}

    Returns: 97337

  36. 9

    {90552,67991,83317,93218,81814,62465,6061,27876,37754,24670,21355,38535,55979,62571,40516,24494,59843,16673,94855,83319,68807,6968,68771,15474,28471,57526,65606,15517}

    Returns: 47451

  37. 45

    {80479,98941,79024,35004,62213,95483,82370,45513,66129,74456,92184,92923,2757,47311,646,22991,72304,98149,28746,39815,94250,39247,1337,52442,21945,34625,65301,86684,28695,50350,92251,11205,9002,51361,8120,34240,42035,56503,78972,61874,92098,2294,91431,57445,86662,34734,24927}

    Returns: 96647

  38. 21

    {97931,90436,97062,25148,71668,51355,16952,91408,96739,34822,59782,47744,27073,14516,87689,74062,96894,19573,17686,63554,33737,66726,76913,23558,19026,15723,94318,98641,59226,56890,40740}

    Returns: 59224

  39. 3

    {48980,15409,52577,34362,84303,60548,10506,38605,99310,41835,80166,66122,55474,19353,56816,11334,43145,9139,30294,96647,80229,44056,10752,88543,15592,55403,52427,84773,46139,45502,82574,7089,99710,45117,60094,40532,93145}

    Returns: 4750

  40. 2

    {5394,16465,75837,61261,68413,3127,15754,88338,73839,55866,78027,10741,83268,48605,5053,54004,48305,56451,58896,18039,47813,88742,43283,8302,28346}

    Returns: 835

  41. 19

    {74615,66072,51103,44378,40091,29895,75924,23249,41944,1198,52168,20207,27961,47213,74188,64018,21249,43795,81393,78707,65478,25885,735,36880,60794,68268,14686,10645}

    Returns: 40882

  42. 20

    {81489,43015,46639,39672,25892,60908,10970,63647,76954,99675,15435,62513,8585,40700,1129,18195,86305,25051,24574,89098,66727}

    Returns: 91090

  43. 12

    {76438,31072,72896,78551,79279,26856,15577,1496,44667,97603,21644,82410,49034,68363,42718,48364,48974,83496,69582,45803,20762,65757,10245,38598,10645,19295,38042,27345,44475,65761,49218,21556,35761,76426,29203,73363,70274,51592,54708}

    Returns: 59441

  44. 3

    {43870,25667,76749,15680,79001,21314,20439,46697,89568,19871,21948,20316,81289,98366,56916,75080,62761,90309,71133,61179,21284,15747,25753,63457,13858,62174,86770,48729,8066,85529,8701,41558,29896,78366,16060,69519,79633,69165,18206,86499,11080,10721,60609,42125,41682}

    Returns: 2216

  45. 19

    {18399,76355,89070,28135,92926,27987,51238,11051,48858,89611,82101,24215,95144,5593,87900,22744,42046,92772,73042,250,92011,97593,78932,66884,40273,18819,87049,83871,15871,44089,29841,21972,93615,19218,10729,72210,52184,16916,6494,7855}

    Returns: 61526

  46. 11

    {97356,6630,73187,61651,35025,45215,1834,77142,1811,31052,91784,89683,76618,70447,1766,19862,32651,49465,70791}

    Returns: 48354

  47. 15

    {65101,95179,83417,2828,18051,98749,1577,60254,74089,4985,35585,70262,43844,65758,11346,46540,84212,56875,35458,22452,6677,83450,27652,63298}

    Returns: 62003

  48. 32

    {76387,88730,19092,1562,59097,58420,94056,81607,14716,27657,23134,2433,7415,47420,45373,97735,67478,24616,37045,49869,88538,65537,25884,91063,41197,88777,97338,98869,5232,7123,91040,95734,21968,60396,79539,76618,76728,53674,76199,3704,84511,3828,6854}

    Returns: 78779

  49. 50

    {90220,22000,56558,12716,81269,52124,62851,83953,84997,84604,39458,71322,808,78046,83372,8571,43758,41903,71001,35393,42258,54651,92364,81767,37480,84911,27377,52871,93283,46912,55733,15117,98048,16292,56162,27303,96306,89373,7382,5753,43,30742,42559,67118,85763,56742,91733,59176,98184,63730}

    Returns: 98141

  50. 3

    {95523,911,4404,69833,22626,64005,94758,97207,86248,78415,78606,57949,52013,87710,26648,77004,9043,40413,49720,84408,5830,43536,56962,18987,64271,12534}

    Returns: 17415

  51. 28

    {62102,80685,86873,95451,27825,93876,88310,2244,85613,18955,96268,33939,46103,51991,98965,66487,54376,38339,44611,53470,59915,6880,22174,14607,74092,90604,704,56663,51167,12913,22825,44092,92682,89988,72127,74253,42800,110,8229,75930,53787,74887,13687,3904,19494,14750}

    Returns: 69710

  52. 44

    {19300,12469,87000,5921,1839,24585,2429,23237,26257,67152,87692,50806,37736,53659,89436,36969,52474,33083,408,4179,6870,87135,51511,75856,25378,59483,94298,16161,24582,28229,17857,53331,22837,7513,9674,3162,97811,381,11559,90749,97799,10878,82362,20010,92190}

    Returns: 97403

  53. 49

    {94634,85113,63510,34904,46383,38581,4430,20223,810,22741,56429,8617,77562,86318,29330,50189,44703,30703,38068,23309,78444,79274,34367,43633,474,52003,25628,41535,29081,78069,21198,94937,22593,15835,26265,44628,31367,62338,37021,70448,4396,43912,49184,6488,42351,84432,62825,29336,93859,50694}

    Returns: 94127

  54. 8

    {66299,39785,74932,26575,41345,52250,82637,60143,47430,3456,3679,17547,11924,89685,64680,30463,55039,35632,42704,43071,43993,98319,695}

    Returns: 43403

  55. 44

    {62913,2126,86006,18436,46542,69979,56952,95179,89444,24543,14613,18422,16415,30516,71452,45909,24595,80304,93018,80356,81689,6087,52173,65017,58900,63757,44225,8439,73503,41688,51401,92127,37749,29059,95483,68422,92764,88911,67400,19233,95566,76485,83062,36957,44262,64599,32924}

    Returns: 80953

  56. 25

    {38180,27706,71416,62973,9594,65491,26171,56994,7797,78856,73800,18698,94886,66066,21793,66143,67311,9019,61900,41890,44106,1145,53056,476,6121,32680,61561,63427,21369,86691,35819,18629,18016,96735,60339,73427,72517,11108,43688,43277,1262,72329,35985,94022,54980,12235,35856,44820,25812,95817}

    Returns: 68275

  57. 46

    {22767,26911,34892,41890,23920,32829,45135,62858,52381,18244,88185,37066,18503,67261,89112,46545,69996,48341,99973,22634,10140,10552,20501,1926,8312,80393,1583,40871,42966,19195,21272,56075,46209,73551,5386,83123,83006,39627,69379,63088,52201,57043,92026,63081,85022,70215}

    Returns: 98390

  58. 10

    {84083,22457,61652,44397,86146,31657,56474,20734,24645,98591,43170,62381,42714,19555,9157,5973,56934,38300,80189,96836,32118,52900,53177,6663,2304,62757,75152,1012,50280}

    Returns: 68726

  59. 25

    {96851,15070,93028,55131,26889,63813,23632,56738,47490,17583,21761,67437,67258,9667,68023,52422,43913,89665,28859,43785,93193,74044,33662,74452,50821,50758,65997}

    Returns: 81781

  60. 11

    {79402,95955,61520,89790,35122,14187,75773,48243,81128,38912,13138,99494,99098,3044,95093,42658,6903,26889,87617,34105,92085,42751,15154,65077,85813,40267,8954,49501,58815,11040,31441,77568,95879}

    Returns: 65414

  61. 38

    {20609,54961,24962,67519,41534,16496,63983,83437,72319,17162,36123,73981,55320,47415,78830,86616,65147,9416,78621,85597,63261,58821,76032,15213,52067,32335,89521,39650,65641,15748,9250,38208,33518,18400,7867,85188,41728,20320,71344,75193,87327,36546,39323}

    Returns: 72359

  62. 17

    {89993,15771,86896,69314,35037,3048,48525,37685,53551,75665,3730,9611,20122,74228,10586,22030,11684,74713,87642,62875,40739,24876,8976,18699,10077}

    Returns: 73891

  63. 2

    {84988,20968,65431,84766,26752,74289,76386,32525,46690,12376,65652,46694,43280,74231,48434,85036,63369,66275,76574,42460,17189,16140}

    Returns: 1381

  64. 13

    {84763,76895,88937,80007,94771,9066,3670,13775,69321,40159,36931,76063,3546,80306,61496,80275,3247,99069,53366,64236,28259,37955,78390,3873,24370,91088,6050,50989,85440,41823,31402,46374,67906,694,10981,98766,50221,17836,50373}

    Returns: 66051

  65. 42

    {63819,19540,79920,2259,90609,16336,83749,79293,49680,9345,52484,50465,18452,66867,17651,18841,64325,51477,61360,85171,88386,29324,84768,71397,26478,33428,13768,78701,43751,19701,48789,66563,13200,24926,84533,72831,80721,72480,42632,22688,11637,56457,33297,14560,96913,11900,59143,59441}

    Returns: 82353

  66. 2

    {9385,16883,31865,8367,52654,7158,47529,57419,42297,30631,48766,539,22219,33817,95794,787,115,57905,26711,22043,95360,87021,23376,70947,70776,68081,40283,15460,12641,29424,90834,85301,48380,48468,89639,65190}

    Returns: 5935

  67. 25

    {1234, 653, 4213, 654, 87, 456, 342, 6, 867, 546, 423, 234, 65, 576, 8, 546, 3, 765, 786, 654, 3, 56, 57, 234, 234, 7, 96, 7, 865, 2341, 123, 53, 645, 774, 432, 543, 197, 864, 54, 23, 6534, 23, 1112, 213, 234, 345, 654, 76, 34, 24 }

    Returns: 6102

  68. 8

    {100, 92, 133, 201, 34, 34, 34, 94, 108, 100, 92, 133, 201, 34, 34, 34, 94, 108, 100, 92, 133, 201, 34, 34, 34, 94, 108, 100, 92, 133, 201, 34, 34, 34, 94, 108, 100, 92, 133, 201, 34, 34, 34, 94, 108, 100, 92, 133, 201, 34 }

    Returns: 107

  69. 10

    {100, 92, 133, 201, 34, 34, 34, 94, 108, 101, 56, 34, 34, 34, 567, 234, 34, 12, 45, 87, 34, 123, 312, 344, 321, 123, 33, 78, 567, 342, 121, 111, 111, 123 }

    Returns: 223

  70. 25

    {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }

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