Statistics

Problem Statement for "SplitIntoPairs"

Problem Statement

You are given a int[] A with N elements, where N is even. Note that some elements of A may be negative. You are also given a int X which is guaranteed to be negative. You must divide the elements of A into N/2 disjoint pairs. (That is, each element of A must be in exactly one of those pairs.) Your goal is to maximize the number of pairs in which the product of the two elements is greater than or equal to X. Return the largest possible number of such pairs.

Definition

Class:
SplitIntoPairs
Method:
makepairs
Parameters:
int[], int
Returns:
int
Method signature:
int makepairs(int[] A, int X)
(be sure your method is public)

Constraints

  • A will contain between 2 and 50 elements, inclusive.
  • The number of elements in A will be even.
  • Each element in A will be between -1,000,000,000 and 1,000,000,000, inclusive.
  • X will be between -1,000,000,000 and -1, inclusive.

Examples

  1. {2,-1}

    -1

    Returns: 0

    One possible pair has product -2, which is lower than needed.

  2. {1,-1}

    -1

    Returns: 1

    Here product is -1, it's enough.

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

    -1

    Returns: 2

    If first pair contains numbers -5 and -4, and second contains 2 and 3, both will have positive product.

  4. {5,-7,8,-2,-5,3}

    -7

    Returns: 3

    Acceptable splitting is {5,8}, {-7,-5} and {-2,3}.

  5. {3,4,5,6,6,-6,-4,-10,-1,-9}

    -2

    Returns: 4

  6. {1000000,1000000}

    -5

    Returns: 1

    Beware overflow.

  7. {905,944,-352,-74,-222,-674,-862,421,-394,-836,204,-686,-673,-931,-750,-986,-798,-854,-271,256,-959,823,924,-912,-892,675,577,83,-16,942,-890,-36,135,-844,159,-583,788,-692,-936,453,-891,310,545,874,827,-311,528,-116,775,-266}

    -1000000000

    Returns: 25

  8. {905,944,-352,-74,-222,-674,-862,421,-394,-836,204,-686,-673,-931,-750,-986,-798,-854,-271,256,-959,823,924,-912,-892,675,577,83,-16,942,-890,-36,135,-844,159,-583,788,-692,-936,453,-891,310,545,874,827,-311,528,-116,775,-266}

    -1

    Returns: 24

  9. {905,944,-352,-74,-222,-674,-862,421,-394,-836,204,-686,-673,-931,-750,-986,-798,-854,-271,256,-959,823,924,-912,-892,675,577,83,-16,942,-890,-36,135,-844,159,-583,788,-692,-936,453,-891,310,545,874,827,-311,528,-116,775,-266}

    -1000

    Returns: 24

  10. {905,944,-352,-74,-222,-674,-862,421,-394,-836,204,-686,-673,-931,-750,-986,-798,-854,-271,256,-959,823,924,-912,-892,675,577,83,-16,942,-890,-36,135,-844,159,-583,788,-692,-936,453,-891,310,545,874,827,-311,528,-116,775,-266}

    -5000

    Returns: 25

  11. {-2,-4,-4,3,0,-4,0,-3,-4,2}

    -1

    Returns: 5

  12. {-2,-4,-4,3,0,-4,0,-3,-4,2}

    -11

    Returns: 5

  13. {-2,-4,-4,13,-20,-24,-10,-23,-14,22,19,5}

    -1

    Returns: 6

  14. {-2,-4,-4,13,-20,-24,-10,-23,14,22,19,5}

    -1

    Returns: 5

  15. {-2,-4,-4,13,-20,-24,-10,-23,14,22,19,5}

    -10

    Returns: 6

  16. {-2,-4,-4,13,-20,-24,-10,-23,14,22,19,5}

    -7

    Returns: 5

  17. {-2,-4,-4,13,-20,-24,-10,-23,-14,22,19,5,-14,12}

    -10

    Returns: 7

  18. {-2,-4,-4,13,-20,-24,-10,-23,-14,22,19,5,-14,12}

    -9

    Returns: 6

  19. {-32,-34,-24,3,-10,-4,-20,-43,-44,22,99,75,-64,-22,-20,90,69,60}

    -1

    Returns: 8

  20. {-32,-34,-24,3,-10,-4,-20,-43,-44,22,99,75,-64,-22,-20,90,69,60}

    -12

    Returns: 9

  21. {-32,-34,-24,3,-10,-4,-20,-43,-44,22,99,75,-64,-22,-20,90,69,60}

    -11

    Returns: 8

  22. {-5,-140,94,-45,-136,-139,193,125,-117,97,-87,-111,199,0,43,135,-37,32,-62,170,-50,-71}

    -1

    Returns: 11

  23. {-5,140,94,-45,-136,-139,193,125,-117,97,-87,-111,199,0,43,135,-37,32,-62,170,-50,-71}

    -1

    Returns: 11

  24. {-5,140,94,-45,-136,-139,193,125,-117,97,-87,-111,199,1,43,135,-37,32,-62,170,-50,-71}

    -1

    Returns: 10

  25. {-5,140,94,-45,-136,-139,193,125,-117,97,-87,-111,199,1,43,135,-37,32,-62,170,-50,-71}

    -5

    Returns: 11

  26. {10818,-18246,-19725,16148,-3747,5706,7572,11962,-9647,17307,-19662,11369,-8048,4235,-8840,1990,13255,9267,-1834,6047,364,-6426,-18250,-4013,14223,14201,4108,-17517,12645,-15571}

    -1

    Returns: 14

  27. {10818,-18246,-19725,16148,-3747,5706,7572,11962,-9647,17307,-19662,11369,-8048,4235,-8840,1990,13255,9267,-1834,6047,364,-6426,-18250,-4013,14223,14201,4108,-17517,12645,-15571}

    -1000

    Returns: 14

  28. {10818,-18246,-19725,16148,-3747,5706,7572,11962,-9647,17307,-19662,11369,-8048,4235,-8840,1990,13255,9267,-1834,6047,364,-6426,-18250,-4013,14223,14201,4108,-17517,12645,-15571}

    -667576

    Returns: 15

  29. {10818,-18246,-19725,16148,-3747,5706,7572,11962,-9647,17307,-19662,11369,-8048,4235,-8840,1990,13255,9267,-1834,6047,364,-6426,-18250,-4013,14223,14201,4108,-17517,12645,-15571}

    -667575

    Returns: 14

  30. {-90122,-98566,-79800,65132,28130,-48626,62512,-3265,-58006,65017,1742,-15971,91502,85961,-7838,-82539,61065,-25210,-67751,64007,34100,-92851,-80892,25607,61762,68730,81961,98653,-75609,7825,-16698,-18369,-641,-77434,-90764,69934,41205,-9213,35087,-81955}

    -1116622

    Returns: 20

  31. {-90122,-98566,-79800,65132,28130,-48626,62512,-3265,-58006,65017,1742,-15971,91502,85961,-7838,-82539,61065,-25210,-67751,64007,34100,-92851,-80892,25607,61762,68730,81961,98653,-75609,7825,-16698,-18369,-641,-77434,-90764,69934,41205,-9213,35087,-81955}

    -1116621

    Returns: 19

  32. {-7726273,-198566,9681506,-6792315,-540917,-4861632,-4982458,-1383709,-6158006,4166470,-6812236,-624690,5158649,-9032251,-8845697,4151603,6274931,-8029271,-5157899,6663477,-1398145,-4257609,145272,-5237570,861762,-4839969,-2853810,577517,-941855,707825,-9448768,-438974,-2454848,9216156,5254895,-923375,440146,3309157,-9364361,8771003}

    -2352133

    Returns: 19

  33. {-872113403,614732258,852780564,-364762495,-766020713,-223899463,-809975595,-171841343,-804547660,932729055,698760645,399517073,874914195,-851687809,620595203,-557170078,85869576,-137114380,-323991217,210123325,-128394235,754027517,548178290,-491028249,620518046,963832152,-935735869,272572641,480306795,995021233,-124979841,-286205860,486682805,-975116828,220156082,343182640,183009133,406271598,674094533,-7665256}

    -1

    Returns: 20

  34. {686014,-140413,38898,453373,-2183,456054,-2401,-5669,916678,3197,-9268,711369,485555,-2143,-3396,761990,514108,-7341,-167232,-138103,-2230,-7733,-673572,-8397,3714,-8765,4878,518458,-139757,3789,2291,-333872,-68453,-408540,6262,684380,303765,2080,-188915,567204,-270568,-608555,-50681,865635,145118,254393,2027,9236,6614,749600}

    -1

    Returns: 24

  35. {686014,-140413,38898,453373,-2183,456054,-2401,-5669,916678,3197,-9268,711369,485555,-2143,-3396,761990,514108,-7341,-167232,-138103,-2230,-7733,-673572,-8397,3714,-8765,4878,518458,-139757,3789,2291,-333872,-68453,-408540,6262,684380,303765,2080,-188915,567204,-270568,-608555,-50681,865635,145118,254393,2027,9236,6614,749600}

    -4343861

    Returns: 25

  36. {686014,-140413,38898,453373,-2183,456054,-2401,-5669,916678,3197,-9268,711369,485555,-2143,-3396,761990,514108,-7341,-167232,-138103,-2230,-7733,-673572,-8397,3714,-8765,4878,518458,-139757,3789,2291,-333872,-68453,-408540,6262,684380,303765,2080,-188915,567204,-270568,-608555,-50681,865635,145118,254393,2027,9236,6614,749600}

    -4343860

    Returns: 24

  37. {686014,-140413,38898,453373,-38,56,23,-27727,543192,40,-90,668783,-749599,-933398,-54,-52,-508107,-60,-21,-733259,91,-383323,-726497,66,794192,92,-798387,514663,-265743,479453,-231752,45,-277329,-508343,-185031,77,541431,-38,506315,49,-330584,-58,25,23,11,27,934481,975269,-899517,739542}

    -1

    Returns: 25

  38. {686014,-140413,38898,453373,12,-325555,-117123,-107,633208,-181,171,39,407808,-770671,401056,218102,-170,-893786,-94,952651,872501,17270,-8,-210819,745846,-60,568424,94,-336277,-197,715750,-35,991206,-25,50,64,47,185,-83700,899759,772864,740070,-808846,-195437,-167236,62,209115,-975701,-143,-522051}

    -1

    Returns: 24

  39. {686014,-140413,38898,453373,12,-325555,-117123,-107,633208,-181,171,39,407808,-770671,401056,218102,-170,-893786,-94,952651,872501,17270,-8,-210819,745846,-60,568424,94,-336277,-197,715750,-35,991206,-25,50,64,47,185,-83700,899759,772864,740070,-808846,-195437,-167236,62,209115,-975701,-143,-522051}

    -96

    Returns: 25

  40. {686014,-140413,38898,453373,12,-325555,-117123,-107,633208,-181,171,39,407808,-770671,401056,218102,-170,-893786,-94,952651,872501,17270,-8,-210819,745846,-60,568424,94,-336277,-197,715750,-35,991206,-25,50,64,47,185,-83700,899759,772864,740070,-808846,-195437,-167236,62,209115,-975701,-143,-522051}

    -95

    Returns: 24

  41. {-872113403,614732258,185,103478667,-60289383,-89,-151,-107,-144398419,46,423704813,179,776887394,40,327617513,266244600,-281619614,-134,850198886,-66,78,-73479329,-151822892,-35,-21,147,-684760088,-157,-194,-552331073,-206234363,398164123,52,-337961681,-603910935,776189072,-795765385,144,109,910709347,494010347,553900800,195,-225114223,532182291,-826578151,-196,-133,-391688045,-107}

    -1

    Returns: 24

  42. {-872113403,614732258,185,103478667,-60289383,-89,-151,-107,-144398419,46,423704813,179,776887394,40,327617513,266244600,-281619614,-134,850198886,-66,78,-73479329,-151822892,-35,-21,147,-684760088,-157,-194,-552331073,-206234363,398164123,52,-337961681,-603910935,776189072,-795765385,144,109,910709347,494010347,553900800,195,-225114223,532182291,-826578151,-196,-133,-391688045,-107}

    -840

    Returns: 25

  43. {-872113403,614732258,852780564,-364762495,-766020713,-223899463,-809975595,-171841343,-804547660,932729055,698760645,399517073,874914195,-851687809,620595203,-557170078,85869576,-137114380,-323991217,210123325,-128394235,754027517,548178290,-491028249,620518046,963832152,-935735869,272572641,480306795,995021233,-124979841,-286205860,486682805,-975116828,220156082,343182640,183009133,406271598,674094533,-7665256,-858260613,-634182631,99794083,-717654287,-181472121,219444548,411507309,658776668,495481341,551580701}

    -1

    Returns: 25

  44. {-872113403,614732258,852780564,-364762495,-766020713,-223899463,-809975595,-171841343,-804547660,932729055,698760645,399517073,874914195,-851687809,620595203,-557170078,85869576,-137114380,-323991217,210123325,-128394235,754027517,548178290,-491028249,620518046,963832152,-935735869,272572641,480306795,995021233,-124979841,-286205860,486682805,-975116828,220156082,343182640,183009133,406271598,-674094533,-7665256,-858260613,-634182631,99794083,-717654287,-181472121,219444548,411507309,658776668,495481341,551580701}

    -1

    Returns: 24

  45. {872113405,614732258,852780564,364762497,766020715,223899465,809975597,171841345,804547662,932729055,698760645,399517073,874914195,851687811,620595203,557170080,85869576,137114382,323991219,210123325,128394237,754027517,548178290,491028251,620518046,963832152,935735871,272572641,480306795,995021233,124979843,286205862,486682805,975116830,220156082,343182640,183009133,406271598,674094533,7665258,858260615,634182633,99794083,717654289,181472123,219444548,411507309,658776668,495481341,551580701}

    -1

    Returns: 25

  46. {-872113403,-614732256,-852780562,-364762495,-766020713,-223899463,-809975595,-171841343,-804547660,-932729053,-698760643,-399517071,-874914193,-851687809,-620595201,-557170078,-85869574,-137114380,-323991217,-210123323,-128394235,-754027515,-548178288,-491028249,-620518044,-963832150,-935735869,-272572639,-480306793,-995021231,-124979841,-286205860,-486682803,-975116828,-220156080,-343182638,-183009131,-406271596,-674094531,-7665256,-858260613,-634182631,-99794081,-717654287,-181472121,-219444546,-411507307,-658776666,-495481339,-551580699}

    -1

    Returns: 25

  47. {-32,-34,-4135,-24,-3704,-92,-12,-4871,-9105,-90}

    -10

    Returns: 5

  48. {34,36,4137,26,3706,94,14,4873,9107,92}

    -10

    Returns: 5

  49. {-2,-4,-4,3,0,-4,0,-3,-4,2}

    -5

    Returns: 5

  50. {-2,-4,-4,3,0,-4,0,-3,-4,2}

    -4

    Returns: 5

  51. {-2,-4,-4,3,0,-4,0,-3,-4,2}

    -3

    Returns: 5

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

    -2

    Returns: 3

  53. {-2,-4,-4,1,7,-4}

    -1

    Returns: 3

  54. {-2,-4,-4,1}

    -3

    Returns: 2

  55. {-2,-4,-4,1}

    -2

    Returns: 2

  56. {-2,-4,-4,1}

    -1

    Returns: 1

  57. {-2,-4,-4,-1}

    -1

    Returns: 2

  58. {-2,-4,-4,-1}

    -2

    Returns: 2

  59. {-1000000000, 1000000000 }

    -1

    Returns: 0

  60. {1000000, 1000000 }

    -5

    Returns: 1

  61. {935079839, -92769986, -8306102, -932447057, 638383088, 195430486, 958789404, -200192420, -675779976, -725013656, 487537753, -364506139, -230743714, -244096319, 368979792, 852765943, -65001679, 472328325, -216011660, -898510362, -169670032, -441020563, 973226413, 379801829, 502688843, -824803519, 26035776, 800950205, 701328047, -721376925, -467093076, 169748305, -815788157, 30984110, -852342833, -630393844, -538584544, -620330733, -311495956, -117251797, -962936339, -463922646, -512528244, 533042035, -868756910, 697644624, 199179204, -314796386, 386284667, -942608797 }

    -712510151

    Returns: 25

  62. {1000000000, -1000000000 }

    -5

    Returns: 0

  63. {10000000, -10000000 }

    -1000000000

    Returns: 0

  64. {-999999999, 999999999 }

    -999999999

    Returns: 0

  65. {1000000000, 1000000000, 1000000000, -1000000000 }

    -1000000000

    Returns: 1

  66. {1, -1 }

    -2

    Returns: 1

  67. {-1000000, 1000000 }

    -5

    Returns: 0

  68. {1000000000, -1000000000 }

    -1

    Returns: 0

  69. {-1000000000, 1000000000 }

    -100000000

    Returns: 0

  70. {-1000000000, -1000000000, -1000000000, 1000000000, 1000000000, 1000000000, -1000000000, -1000000000, -1000000000, 1000000000, 1000000000, 1000000000, -1000000000, -1000000000, -1000000000, 1000000000, 1000000000, 1000000000, -1000000000, -1000000000, -1000000000, 1000000000, 1000000000, 1000000000, -1000000000, -1000000000, -1000000000, 1000000000, 1000000000, 1000000000, -1000000000, -1000000000, -1000000000, 1000000000, 1000000000, 1000000000, -1000000000, -1000000000, -1000000000, 1000000000, 1000000000, 1000000000, -1000000000, -1000000000, -1000000000, 1000000000, 1000000000, 1000000000, -1000000000, 1000000000 }

    -1

    Returns: 24

  71. {1000000000, -1000000000 }

    -1000000000

    Returns: 0

  72. {1000000000, -1000000000 }

    -10000

    Returns: 0

  73. {-1000000000, -1000000000, -1000000000, 1000000000, 1000000000, 1000000000 }

    -10000

    Returns: 2

  74. {1000000000, -1000000000 }

    -2

    Returns: 0

  75. {1330467, -20271450 }

    -1

    Returns: 0

  76. {-1000000000, 1000000000 }

    -1000000000

    Returns: 0

  77. {1000000, -1000000 }

    -1

    Returns: 0

  78. {-1000000000, -1000000000, 1, 2 }

    -2

    Returns: 2

  79. {-1000000000, -1000000000, -1000000000, 240, 360, 480 }

    -1

    Returns: 2

  80. {10, -10 }

    -100

    Returns: 1

  81. {-1, -1, 1, 1, 0, 0 }

    -10

    Returns: 3

  82. {-66666666, 123 }

    -2

    Returns: 0

  83. {1000000000, 1000000000 }

    -5

    Returns: 1

  84. {-1000000000, 1000000000 }

    -500

    Returns: 0

  85. {-1000000000, 1000000000 }

    -18

    Returns: 0

  86. {1, 1, -1, -1 }

    -1

    Returns: 2

  87. {1000000000, -1000000000, 999999999, -999999999, 999999998, -999999998 }

    -1

    Returns: 2

  88. {536870912, -40000000 }

    -1

    Returns: 0

  89. {0, -1 }

    -1

    Returns: 1

  90. {0, 0, 0, 0 }

    -1

    Returns: 2

  91. {10000, -300000 }

    -1000000000

    Returns: 0

  92. {0, 0, 0, 0, 0, 0 }

    -10

    Returns: 3

  93. {-1000000, 1000000 }

    -1

    Returns: 0

  94. {-1000000000, 1000000000 }

    -999999999

    Returns: 0

  95. {-1000000000, -1000000000, -1000000000, 1000000000, 1000000000, 1000000000 }

    -1

    Returns: 2

  96. {3, 3, 3, 3, 3, 3, 3, 3 }

    -2

    Returns: 4

  97. {1, -1 }

    -1

    Returns: 1

  98. {-10000, 0 }

    -1

    Returns: 1

  99. {-10, 8, -4, -1 }

    -20

    Returns: 2

  100. {-10000000, 10000000 }

    -1000000000

    Returns: 0

  101. {-3, 8 }

    -14

    Returns: 0

  102. {-1000000000, 1000000000, 3, 4 }

    -1

    Returns: 1

  103. {1000000000, -1000000000 }

    -99999999

    Returns: 0

  104. {-2, -1, 1, 2 }

    -100

    Returns: 2

  105. {-2, 0, 3, 1 }

    -1

    Returns: 2

  106. {0, -2, 5, -9, 9, -77 }

    -1

    Returns: 3

  107. {-1000000000, 1000000000 }

    -2

    Returns: 0

  108. {-10, 501520000 }

    -720232704

    Returns: 0

  109. {-3, 4 }

    -7

    Returns: 0

  110. {-3, -2, -1, 0, 1, 2, 3, 4 }

    -1

    Returns: 4

  111. {0, 0, 0, -1 }

    -1000

    Returns: 2

  112. {-1000000000, -1000000000, -1000000000, 1000000000, 1000000000, 1000000000 }

    -1000000000

    Returns: 2

  113. {-1000000000, -1000000000, 1000000000, -1000000000, 1000000000, 1000000000 }

    -1000000000

    Returns: 2

  114. {0, 0 }

    -100

    Returns: 1

  115. {-5000000, -2, -1, 5000000, 5000000, 5000000 }

    -10

    Returns: 2

  116. {-1000000000, -1000000000 }

    -2

    Returns: 1

  117. {-10, -20, 0, 0 }

    -10

    Returns: 2

  118. {-1000000000, -1000000000 }

    -1

    Returns: 1

  119. {-1000000000, 3 }

    -1

    Returns: 0

  120. {30000, -100000 }

    -1

    Returns: 0

  121. {1000000000, 1000000000, 1000000000, -1000000000 }

    -4

    Returns: 1

  122. {-4, -1, 0, 2 }

    -4

    Returns: 2

  123. {-1000000000, 3 }

    -10000

    Returns: 0

  124. {0, 0, 0, 1 }

    -1

    Returns: 2

  125. {0, 0, -2, -2 }

    -1

    Returns: 2

  126. {999999999, -999999999 }

    -999999999

    Returns: 0

  127. {100000000, -100000000 }

    -187491942

    Returns: 0

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

    -3

    Returns: 2

  129. {1000000000, -1000000000, -1000000000, -1000000000 }

    -5

    Returns: 1

  130. {-5, -5, -5, -5, -2, -1, 1, 2, 5, 5, 5, 5 }

    -4

    Returns: 6

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: