Statistics

Problem Statement for "DollSets"

Problem Statement

A doll vendor has just received a shipment of dolls from the factory. Their sizes are given in the int[] dollSizes. The vendor can only sell dolls in sets of two such that one doll is K times as large as the other. What is the maximum number of sets that the vendor can assemble? Each doll can only be used in a single set.

Definition

Class:
DollSets
Method:
maximumQuantity
Parameters:
int[], int
Returns:
int
Method signature:
int maximumQuantity(int[] dollSizes, int K)
(be sure your method is public)

Constraints

  • dollSizes will contain between 1 and 50 elements, inclusive.
  • Each element in dollSizes will be between 1 and 1000000, inclusive.
  • K will be between 1 and 25, inclusive

Examples

  1. {1,2,1,2,4}

    2

    Returns: 2

    There are two possible ways to construct two sets: ({1,2},{1,2}) and ({1,2},{2,4}).

  2. {5,4,3,2,1}

    2

    Returns: 1

    You can construct either set {1,2} or set {2,4}.

  3. {5,4,1,2,3,4,5,67,8,9,8,7,15,12}

    3

    Returns: 3

  4. {1}

    25

    Returns: 0

  5. {1,9,81,729,1,81}

    9

    Returns: 2

  6. {1}

    1

    Returns: 0

  7. {2,1}

    1

    Returns: 0

  8. {1,2,2}

    1

    Returns: 1

  9. {3,4,1,1}

    1

    Returns: 1

  10. {1,5,5,3,1}

    1

    Returns: 2

  11. {1,1,3,5,1,2}

    1

    Returns: 1

  12. {2,5,7,1,4,6,6}

    1

    Returns: 1

  13. {2,1,4,1,3,3,2,7}

    1

    Returns: 3

  14. {7,5,9,5,6,8,3,8,8}

    1

    Returns: 2

  15. {10,7,4,3,6,2,10,4,6,10}

    1

    Returns: 3

  16. {8,5,3,4,3,5,3,3,7,1,2}

    1

    Returns: 3

  17. {12,7,7,8,7,2,10,3,2,8,9,6}

    1

    Returns: 3

  18. {13,11,6,7,4,6,12,6,10,3,4,4,4}

    1

    Returns: 3

  19. {2,5,10,14,11,1,2,4,10,3,3,10,8,11}

    1

    Returns: 4

  20. {7,2,12,6,6,10,6,1,1,3,15,9,6,9,13}

    2

    Returns: 3

  21. {3,11,5,6,3,10,9,15,1,3,5,15,11,16,6,13}

    2

    Returns: 3

  22. {12,9,17,9,2,11,16,7,11,2,12,6,4,11,16,9,17}

    2

    Returns: 2

  23. {10,4,18,3,8,5,7,17,18,11,4,4,12,14,12,1,12,8}

    2

    Returns: 4

  24. {18,14,6,6,5,9,2,6,15,17,4,17,10,2,3,4,6,13,3}

    2

    Returns: 6

  25. {15,7,4,4,16,17,17,13,6,13,3,19,19,7,12,15,15,6,1,8}

    2

    Returns: 3

  26. {11,15,18,7,20,20,8,4,18,20,11,2,6,16,9,13,16,20,9,17,19}

    2

    Returns: 4

  27. {22,21,21,7,12,1,7,17,21,20,22,1,6,9,9,18,9,14,22,7,6,20}

    2

    Returns: 3

  28. {20,15,15,12,15,8,19,3,19,16,3,21,23,15,8,19,4,17,5,10,13,21,20}

    2

    Returns: 3

  29. {3,13,11,11,20,10,12,8,4,12,3,14,21,13,10,17,12,19,2,13,5,14,11,20}

    2

    Returns: 3

  30. {6,19,22,18,15,19,8,1,9,8,9,7,25,8,3,16,17,15,8,12,8,16,9,11,7}

    2

    Returns: 5

  31. {15,17,25,9,11,23,15,13,1,25,10,1,24,20,2,13,25,10,13,13,8,15,22,24,15,9}

    2

    Returns: 3

  32. {2,8,16,4,4,1,8,19,17,13,7,11,26,6,6,5,20,26,1,6,19,17,15,17,9,16,8}

    2

    Returns: 5

  33. {27,10,17,5,6,23,7,2,22,1,21,28,6,8,10,5,27,12,28,10,24,18,1,22,10,4,28,18}

    2

    Returns: 5

  34. {9,1,19,28,11,5,2,26,1,23,25,2,15,3,22,19,4,19,25,27,18,18,29,24,17,12,25,29,13}

    2

    Returns: 6

  35. {19,4,11,15,23,6,23,9,13,13,20,14,27,25,28,27,10,14,2,15,21,8,22,22,21,14,7,8,30,17}

    3

    Returns: 4

  36. {13,8,9,9,22,16,5,31,23,12,20,29,16,22,12,3,6,4,31,1,16,5,12,14,20,10,18,30,3,18,18}

    3

    Returns: 5

  37. {5,22,18,10,30,19,6,23,14,12,10,23,29,6,3,20,23,6,29,7,32,9,15,3,20,22,14,14,21,24,25,21}

    3

    Returns: 5

  38. {2,22,9,25,9,32,18,25,20,21,19,5,28,17,17,20,3,20,23,6,25,25,25,4,16,19,29,9,19,12,6,23,16}

    3

    Returns: 4

  39. {8,33,4,27,15,32,17,13,8,2,21,33,23,34,27,19,3,33,16,7,32,17,1,2,33,20,13,25,18,4,28,28,10,4}

    3

    Returns: 2

  40. {26,24,3,3,7,20,3,32,6,29,12,34,2,4,26,15,12,8,10,20,12,20,26,30,18,35,12,16,30,34,18,14,16,13,16}

    3

    Returns: 4

  41. {11,22,36,18,2,30,24,8,14,14,1,10,12,26,10,19,19,11,36,19,33,12,12,22,20,22,33,12,24,10,3,9,6,22,11,2}

    3

    Returns: 8

  42. {11,13,19,36,3,7,2,24,4,19,5,26,17,28,16,35,7,4,19,7,26,22,11,12,11,34,22,11,28,34,31,20,35,22,16,1,1}

    3

    Returns: 2

  43. {38,35,31,27,13,38,4,36,23,13,9,21,9,22,18,24,38,9,28,8,18,35,13,5,24,6,34,6,37,9,5,11,30,25,12,32,22,5}

    3

    Returns: 5

  44. {29,17,30,19,38,32,26,20,26,10,28,12,9,31,29,29,9,10,3,33,25,21,19,16,18,17,23,4,39,39,19,19,29,24,16,11,18,26,19}

    3

    Returns: 4

  45. {31,38,32,10,3,16,12,38,7,30,22,18,21,16,33,6,21,1,21,11,12,16,34,14,9,19,7,38,34,18,15,7,19,7,13,19,30,40,7,5}

    3

    Returns: 8

  46. {23,10,27,41,8,25,36,7,14,31,21,33,41,18,37,8,25,33,27,5,17,9,34,31,22,12,39,23,1,18,26,24,16,38,29,17,22,28,24,12,12}

    3

    Returns: 5

  47. {18,2,36,37,2,33,11,30,9,2,5,29,11,27,32,28,30,25,9,25,23,34,8,17,21,39,38,30,22,21,10,32,33,5,19,17,31,9,41,5,36,38}

    3

    Returns: 4

  48. {11,37,25,21,31,25,12,24,21,24,26,42,6,5,30,19,35,5,36,38,18,25,28,30,25,7,41,16,10,12,31,14,33,22,41,22,12,42,16,13,32,37,34}

    3

    Returns: 6

  49. {7,14,24,17,39,19,11,4,7,1,26,7,14,24,24,2,37,43,10,5,39,27,26,16,32,41,2,37,2,9,37,8,3,38,27,19,14,38,6,5,20,24,34,42}

    3

    Returns: 5

  50. {33,44,30,23,6,30,2,4,30,13,35,33,4,35,34,21,26,8,4,11,34,21,6,30,27,21,30,31,34,36,25,12,18,19,1,10,9,43,2,42,41,33,23,21,23}

    4

    Returns: 4

  51. {3,6,15,16,11,9,17,23,25,35,28,24,11,3,4,38,8,16,36,39,42,27,10,38,45,17,29,28,15,42,10,11,41,11,26,18,5,41,9,32,12,29,2,42,18,7}

    4

    Returns: 6

  52. {26,32,29,10,16,10,36,15,5,27,46,13,33,36,3,44,5,17,43,10,47,33,13,11,5,26,36,30,31,29,11,33,40,26,11,42,30,5,39,17,27,16,10,29,6,20,40}

    4

    Returns: 4

  53. {5,17,22,3,23,4,32,21,7,43,45,19,33,2,5,34,36,19,20,43,16,12,37,30,30,12,16,7,6,29,13,25,17,42,35,38,29,2,34,17,22,37,9,42,7,11,37,40}

    4

    Returns: 4

  54. {1,31,48,28,28,45,46,24,22,15,7,10,13,6,14,23,10,24,36,41,1,33,34,8,42,14,11,1,26,24,46,25,30,14,42,46,17,26,20,43,29,42,6,32,34,44,40,39,26}

    4

    Returns: 6

  55. {21,14,46,34,49,14,29,8,19,33,36,24,44,2,9,13,42,46,8,15,14,40,21,6,30,9,16,1,24,38,14,45,45,48,25,5,16,15,30,27,1,8,42,9,11,20,39,8,28,13}

    4

    Returns: 5

  56. {176,134,89,3,27,1,65,198,143,22,147,14,52,95,57,166,76,133,74,92,44,102,193,103,111,130,177,121,24,86,90,15,12,79,130,69,129,112,27,134,95,39,76,49,154,169,183,48,177,198}

    3

    Returns: 2

  57. {571,178,430,470,89,59,469,472,531,378,589,152,519,402,268,506,288,549,68,400,435,486,139,290,508,85,47,577,510,142,360,73,570,454,534,1,487,540,585,8,416,264,192,542,283,323,369,468,125,258}

    3

    Returns: 1

  58. {517842,670035,163952,629137,586686,154382,511700,357108,715125,767190,22956,195728,705468,227844,89931,115776,589805,918004,967014,325228,90718,335813,356237,757652,313058,886828,531380,70972,357929,370101,304752,957684,568003,1752,459965,576643,50305,730804,161979,77232,419836,626667,975674,656364,199919,856857,339754,53983,831871,100785}

    3

    Returns: 0

  59. {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,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

    Returns: 25

  60. {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,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}

    25

    Returns: 0

  61. {639909,416709,931550,98393,834065,312962,639909,599753,607654,836230,836230,599753,741862,729253,741862,717756,416709,865179,338962,865179,717756,187435,776281,776281,312962,736044,834065,36741,338962,931550,562666,36741,187435,397524,729253,98393,397524,607654,736044,562666}

    1

    Returns: 20

  62. {228991,83919,774364,196058,934418,252900,468360,188692,776150,72288,453319,414680,133182,193760,15708,10592,388075,207340,817884,467209,234180,96880,185293,370586,154386,377384,449747,21184,387182,167838,899494,599982,7854,77193,457982,98029,126450,906638,299991,266364,408942}

    2

    Returns: 20

  63. {951480,615489,645936,205163,104805,972753,111850,74592,747348,941316,129104,103755,311265,154251,215312,27048,696249,174194,202544,313772,249116,9016,651777,279481,607632,335550,30889,522582,34935,92667,324251,24864,317160,387312,232083,213507,838443,51417,217259,710427,236809,640521}

    3

    Returns: 21

  64. {47703,207731,57111,39383,195482,239964,155629,190768,75823,190100,84545,157532,181125,347032,47692,213744,975752,86758,171688,551024,608124,622516,724500,243938,228444,42922,303292,939548,137756,760400,959856,795556,73969,338180,234887,830924,185451,190812,781928,295876,152031,741804,198889}

    4

    Returns: 21

  65. {139666,804750,998925,118030,693560,748245,829660,683485,548695,111043,581250,260975,158409,29331,199785,438575,160950,465820,136697,298745,138712,59749,151042,698330,165932,87715,555215,755210,93164,107947,32578,792045,146655,539735,162890,111471,109739,149649,590150,380980,76196,116250,557355,52195}

    5

    Returns: 22

  66. {55490,105244,631464,693720,97722,272724,45454,43405,624660,94204,57897,347382,769758,128293,116448,886428,32169,193014,332940,88445,104106,9871,823926,698688,59226,260430,194964,136476,104110,162750,147738,58934,624636,183,586332,137321,1098,135158,810948,976500,353604,530670,22746,115620,32494}

    6

    Returns: 22

  67. {393092,447713,34846,202216,746193,106599,39406,275842,100910,41302,56156,110432,91132,24423,42515,637924,63959,954030,136290,15776,4261,83602,139888,113456,706370,29239,19984,132251,289114,476966,59071,413497,68138,16208,125964,170961,120939,4177,585214,28888,18893,881748,243922,846573,29827,297605}

    7

    Returns: 23

  68. {87204,401424,356800,59627,926528,403080,114619,477016,53997,82126,50385,742080,34142,431976,942512,35212,50092,31674,44914,64124,115816,657008,8502,802280,640872,761832,92760,359312,345512,43189,82064,117814,95229,512992,656512,281696,68016,368048,273136,697632,44600,916952,100285,46006,50178,80109,400736}

    8

    Returns: 23

  69. {33818,58461,20508,124965,939537,615015,871947,848394,13885,888372,14646,638370,70930,78045,840438,304362,702405,50488,98181,644904,93382,30417,104428,230643,169011,184572,526149,71656,98708,25627,131814,18779,794646,273753,68335,939852,94266,59294,104393,96883,82932,746388,454392,883629,823707,88294,533646,91523}

    9

    Returns: 24

  70. {924200,76493,63863,373640,9979,668700,55480,51,510,37364,497190,909960,49035,673450,30348,512070,92420,90996,764930,94794,55330,5548,464980,638630,58223,582230,49719,12569,60381,490350,51207,30665,196980,486770,125690,603810,66870,46498,534280,19698,53428,67345,75459,947940,48677,754590,303480,553300,99790}

    10

    Returns: 24

  71. {600314,90119,85154,57772,85217,623414,827002,75730,53456,623832,952391,753005,54574,202202,56674,635492,56712,885665,55301,588016,13141,511566,55441,80515,35294,68277,135278,46506,773586,991309,148577,608311,231616,833030,70326,61555,937387,18382,12298,86581,6207,609851,936694,75182,21056,144551,13507,68455,677105,388234}

    11

    Returns: 25

  72. {656400,23411,25355,21860,22627,145800,34664,24586,382725,773500,416400,5832,26256,10760,565675,1448,337800,15309,976325,37015,706875,2280,21175,16656,614650,925375,160025,269000,526075,871300,568775,180250,34852,30565,57000,529375,546500,6401,866600,36200,28275,585275,13512,764125,21043,633875,30940,7210,22751,39053}

    25

    Returns: 25

  73. {8559,797550,266575,666300,22079,417275,26634,195100,2439,26652,10161,665850,3043,2276,254025,234225,34703,551975,266100,31902,73400,56900,7804,30295,10644,12682,334050,740500,76075,60975,757375,16691,27660,790100,31604,712325,32269,13362,10663,28493,29620,867575,317050,388300,9369,691500,213975,806725,2936,15532}

    25

    Returns: 25

  74. {126224,45551,39129,273903,85295,11638,477428,109221,81466,318857,34003,73909,19235,30520,386,12185,221452,20089,17867,100414,746368,2702,110379,108424,51348,125069,140623,84405,47538,47719,106624,43061,42960,101496,97111,2321,68204,118655,702898,126063,238021,31636,59816,883568,11038,134645,113635,135251,88633,213640}

    7

    Returns: 15

  75. {81739,348585,432050,176317,135599,644315,78766,199137,69717,518320,881585,163001,121516,393830,197333,143049,85680,941800,98461,160150,684940,28799,103664,130627,986665,170990,188360,492305,110133,607580,160633,20913,408695,86410,136988,128750,181149,198540,102473,992700,33172,149870,128863,800750,111720,164975,181100,106786,1167,428400}

    5

    Returns: 15

  76. {51497,56413,600006,38249,78266,717860,674894,32235,54546,13181,62150,29319,60021,186813,79240,21644,65855,8162,36767,25033,22972,620543,30026,67702,39953,161887,330286,31046,85899,439483,26227,38429,566467,65260,61009,49274,542014,14717,32486,322509,61354,49361,933295,16983,341506,71278,252692,84845,20492,275363}

    11

    Returns: 15

  77. {1, 9, 81, 729, 1, 81 }

    9

    Returns: 2

  78. {1, 2, 1, 2, 1, 2 }

    2

    Returns: 3

  79. {1 }

    1

    Returns: 0

  80. {1, 2, 2, 4, 8, 1 }

    2

    Returns: 3

  81. {5, 3, 2, 8, 1, 16, 6, 8, 4, 10, 2, 5, 3, 2, 8, 1, 16, 6, 8, 4, 10, 2, 5, 3, 2, 8, 1, 16, 6, 8, 4, 10, 2, 5, 3, 2, 8, 1, 16, 6, 8, 4, 10, 2, 5, 3, 2, 8, 1 }

    2

    Returns: 21

  82. {2, 4, 1, 8, 2, 4, 1, 8, 2, 4, 2, 4, 1, 8, 2, 4, 1, 8, 2, 4, 2, 4, 1, 8, 2, 4, 1, 8, 2, 4, 2, 4, 1, 8, 2, 4, 1, 8, 2, 4, 2, 4, 1, 8, 2, 4, 1, 8, 2, 4 }

    2

    Returns: 25

  83. {1, 1, 1, 1, 1 }

    1

    Returns: 2

  84. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536 }

    2

    Returns: 10

  85. {2, 4, 1, 8 }

    2

    Returns: 2

  86. {1, 1, 1, 1, 1, 1, 1, 1, 2 }

    2

    Returns: 1

  87. {4, 2, 1, 8 }

    2

    Returns: 2

  88. {7, 22 }

    3

    Returns: 0

  89. {4, 2, 1, 8, 4, 2, 1, 8, 4, 2, 4, 2, 1, 8, 4, 2, 1, 8, 4, 2, 4, 2, 1, 8, 4, 2, 1, 8, 4, 2, 4, 2, 1, 8, 4, 2, 1, 8, 4, 2, 4, 2, 1, 8, 4, 2, 1, 8, 4, 2 }

    2

    Returns: 25

  90. {1, 2, 1, 2, 4, 4, 8, 8, 8, 2, 1, 4, 6, 8, 2, 16, 16, 32, 32, 64, 64, 64, 128, 128, 64, 8, 256, 256 }

    2

    Returns: 12

  91. {1, 2, 2 }

    1

    Returns: 1

  92. {2, 4, 1, 8, 20, 40, 10, 80 }

    2

    Returns: 4

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

    1

    Returns: 5

  94. {3, 9, 1, 9, 27, 27 }

    3

    Returns: 3

  95. {1, 1, 2, 2, 2, 4 }

    2

    Returns: 3

  96. {1, 2, 2, 4, 4, 8, 8, 16, 16, 16, 16, 32, 32, 32, 64, 64, 64, 8, 4, 16, 32, 64, 128, 128, 356, 256, 512, 512, 8, 4, 2, 5, 3, 16, 10, 6, 13, 32, 128, 256, 512, 1, 1, 2, 4, 8, 16, 32, 64, 128 }

    2

    Returns: 23

  97. {1, 2, 1, 2, 4 }

    2

    Returns: 2

  98. {2, 4, 24, 12, 1, 48, 8, 6 }

    2

    Returns: 4

  99. {5, 4, 1, 2, 3, 4, 5, 67, 8, 9, 8, 7, 15, 12 }

    3

    Returns: 3

  100. {1, 1000000 }

    5

    Returns: 0

  101. {1, 1, 1, 1, 1, 1 }

    1

    Returns: 3

  102. {1, 1, 1, 1 }

    1

    Returns: 2

  103. {1, 3 }

    3

    Returns: 1

  104. {3, 9, 1, 27 }

    3

    Returns: 2

  105. {52536, 743257, 2, 6225, 999999, 352, 4672, 7555, 52225, 1330, 8900, 980, 50, 4453, 2553, 647437, 636657, 265662, 1, 1, 1, 1, 1, 1, 1, 1, 9999, 45, 2, 4, 6, 2, 222333 }

    1

    Returns: 5

  106. {1, 3, 1 }

    3

    Returns: 1

  107. {1, 2, 1, 2, 4, 1, 2 }

    2

    Returns: 3

  108. {1, 2, 2 }

    2

    Returns: 1

  109. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    1

    Returns: 7

  110. {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, 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 }

    1

    Returns: 25

  111. {2, 4, 1, 8, 2, 2, 4, 1, 8, 2, 2, 4, 1, 8, 2, 2, 4, 1, 8, 2, 2, 4, 1, 8, 2, 2, 4, 1, 8, 2, 2, 4, 1, 8, 2, 2, 4, 1, 8, 2, 2, 4, 1, 8, 2, 2, 4, 1, 8, 2 }

    2

    Returns: 20

  112. {1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 6, 1, 2, 7, 14, 12, 24, 12, 24, 12, 3, 6, 3, 6, 3, 6, 3, 6, 6 }

    2

    Returns: 24

  113. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }

    1

    Returns: 20

  114. {2, 1, 1, 1, 1, 2 }

    1

    Returns: 3

  115. {1, 2, 4, 8 }

    2

    Returns: 2

  116. {1, 1, 1, 1, 1, 1, 1, 1 }

    1

    Returns: 4

  117. {1, 3, 3 }

    3

    Returns: 1

  118. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    1

    Returns: 5

  119. {2, 1, 3, 5, 4, 8, 16, 8, 32, 16, 32, 64, 128, 64, 512, 64, 128, 8, 4, 2, 1, 8, 16, 32, 64, 128, 256, 512, 512, 128, 64, 4, 10, 8, 9, 18, 36, 72, 144, 36, 128, 356, 512, 2, 4, 8, 16, 64, 128, 64 }

    2

    Returns: 21

  120. {9, 3, 1, 27 }

    3

    Returns: 2

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: