Statistics

Problem Statement for "ManySquares"

Problem Statement

You found a box from an old game. The box contains a lot of sticks and a manual. Frustrated by the fact the manual was unreadable, you decided to invent your own game with the sticks. In your game, the goal is to use the sticks to build as many squares as possible. There are only two rules:
  • Each stick can only be used in one square.
  • Each square must consist of exactly 4 sticks. That is, you cannot combine two or more sticks to create one side of the square.
You are given a int[] sticks. The elements of sticks are the lengths of the sticks you have. Return the maximum number of squares you can make.

Definition

Class:
ManySquares
Method:
howManySquares
Parameters:
int[]
Returns:
int
Method signature:
int howManySquares(int[] sticks)
(be sure your method is public)

Notes

  • If you can't make any square, return 0.

Constraints

  • sticks will contain between 1 and 50 elements.
  • Each element of sticks will be between 1 and 1000, inclusive.

Examples

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

    Returns: 1

    You can build a square with side 1.

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

    Returns: 1

    You can build a square with side 10. You cannot build a square with side 4. (Note that you are not allowed to use 3+1 instead of a 4.)

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

    Returns: 3

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

    Returns: 0

    Sometimes you can't make any square.

  5. {43}

    Returns: 0

  6. {379}

    Returns: 0

  7. {71}

    Returns: 0

  8. {181}

    Returns: 0

  9. {371}

    Returns: 0

  10. {715}

    Returns: 0

  11. {404,404}

    Returns: 0

  12. {942,942}

    Returns: 0

  13. {166,363}

    Returns: 0

  14. {999,746}

    Returns: 0

  15. {16,677}

    Returns: 0

  16. {902,618}

    Returns: 0

  17. {703,703,703}

    Returns: 0

  18. {441,67,67}

    Returns: 0

  19. {766,421,586}

    Returns: 0

  20. {421,859,62}

    Returns: 0

  21. {12,12,468}

    Returns: 0

  22. {641,511,575}

    Returns: 0

  23. {191,191,191,191}

    Returns: 1

  24. {539,800,539,539}

    Returns: 0

  25. {138,603,603,652}

    Returns: 0

  26. {790,417,417,946}

    Returns: 0

  27. {521,460,283,509}

    Returns: 0

  28. {511,746,941,511}

    Returns: 0

  29. {100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100}

    Returns: 5

  30. {380,472,472,380,380,380,472,472,380,472,380,472,472,380,380,380,472,472,380,380,380,472,472}

    Returns: 5

  31. {819,93,819,819,819,819,149,93,93,93,93,819,93,93,93,149,819,819,93,819,149,93,149}

    Returns: 5

  32. {525,887,671,64,671,64,671,525,525,389,64,525,525,671,64,887,525,64,389,389,64,671,64}

    Returns: 3

  33. {435,304,258,435,203,304,510,382,235,258,203,235,304,203,398,203,273,258,382,203,304,510,510}

    Returns: 2

  34. {259,403,459,403,813,67,717,98,459,63,446,847,540,945,219,966,477,758,935,546,485,403,555}

    Returns: 0

  35. {105,105,105,105,105,105,105,105,105,105,105,105,105,105,105,105,105,105,105,105}

    Returns: 5

  36. {11,11,11,625,625,11,625,625,625,11,11,625,11,11,625,625,625,625,11,11}

    Returns: 4

  37. {791,315,315,791,166,166,166,315,166,791,166,791,166,315,315,791,166,791,791,791}

    Returns: 4

  38. {315,568,315,789,568,55,315,789,315,315,55,55,789,315,568,55,789,55,476,476}

    Returns: 3

  39. {30,475,475,147,477,475,475,857,857,385,858,475,882,858,882,911,911,857,385,626}

    Returns: 1

  40. {275,629,837,381,205,946,347,593,903,586,865,860,388,501,197,878,245,837,593,929}

    Returns: 0

  41. {798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798,798}

    Returns: 7

  42. {894,219,894,894,219,894,219,894,219,894,219,219,219,219,219,219,219,894,894,894,894,219,219,219,894,219,894,894,894,219,219}

    Returns: 7

  43. {890,416,890,416,890,273,416,890,273,273,416,273,416,416,416,273,890,890,273,890,416,890,890,890,890,890,416,416,273,416,273}

    Returns: 7

  44. {719,369,369,719,719,280,280,280,958,369,369,719,958,719,369,958,719,958,958,369,844,719,958,280,280,844,844,369,369,958,369}

    Returns: 5

  45. {117,11,11,411,117,655,246,246,117,517,118,118,794,117,655,411,411,594,118,232,655,517,594,232,117,594,246,411,411,517,117}

    Returns: 2

  46. {886,805,153,300,361,361,660,32,760,818,805,77,624,859,869,756,104,624,408,869,36,839,37,818,1,543,869,820,297,280,222}

    Returns: 0

  47. {964,964,964,964,964,964,964,964,964}

    Returns: 2

  48. {545,72,545,545,72,545,72,72,545}

    Returns: 2

  49. {981,478,478,478,478,89,478,478,478}

    Returns: 1

  50. {121,991,675,276,121,276,39,276,39}

    Returns: 0

  51. {487,229,853,853,853,900,853,553,358}

    Returns: 1

  52. {918,965,757,684,489,442,979,194,311}

    Returns: 0

  53. {805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805,805}

    Returns: 9

  54. {853,853,604,853,604,604,853,853,853,604,604,604,853,604,853,853,853,604,604,853,853,604,604,604,604,853,604,853,853,853,604,604,604,853,604,604,853}

    Returns: 8

  55. {636,636,636,636,710,710,710,710,533,636,636,710,533,710,636,533,710,710,710,710,710,636,710,533,533,533,533,533,533,636,533,710,636,636,636,636,533}

    Returns: 8

  56. {48,908,48,253,30,48,908,24,253,253,24,30,908,253,908,253,24,30,24,908,253,908,253,253,48,253,908,24,48,24,253,24,24,48,24,24,48}

    Returns: 6

  57. {738,76,146,628,205,76,333,282,646,738,646,282,205,998,76,628,333,998,205,998,205,205,282,628,333,738,76,738,205,282,76,333,76,998,628,282,282}

    Returns: 7

  58. {351,21,351,144,35,594,601,601,554,90,411,171,785,496,270,70,433,578,94,167,220,90,295,837,327,220,656,90,819,336,493,351,501,282,969,969,282}

    Returns: 0

  59. {958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958,958}

    Returns: 12

  60. {75,75,75,75,327,75,327,327,327,75,327,75,75,327,327,75,75,75,75,327,75,327,75,75,75,327,327,327,75,75,75,75,75,327,327,75,75,75,327,327,75,75,327,75,327,75,327,327}

    Returns: 12

  61. {752,180,180,642,642,642,180,180,752,180,642,752,642,642,180,752,180,642,752,180,180,180,642,752,642,752,642,642,642,752,752,180,752,642,180,642,180,752,642,642,180,642,180,180,642,180,642,180}

    Returns: 10

  62. {750,750,587,587,750,488,344,750,587,344,488,587,970,344,750,970,488,344,488,750,970,750,587,970,750,587,587,750,344,970,750,750,750,750,970,488,587,344,488,344,970,587,587,587,970,750,587,344}

    Returns: 11

  63. {196,196,54,54,196,141,209,209,876,54,71,54,209,509,422,498,876,509,509,71,54,54,141,141,71,509,498,141,196,509,71,71,209,422,196,141,71,422,209,422,802,498,209,54,71,141,54,509}

    Returns: 8

  64. {347,690,109,145,885,145,555,305,680,318,636,476,877,395,850,332,442,775,305,815,775,304,350,422,141,772,891,212,772,885,377,395,901,625,885,413,52,443,413,726,901,106,690,443,332,20,106,275}

    Returns: 0

  65. {179,179,179,179,179,179,179,179,179,179,179,179,179,179,179,179,179,179,179,179,179,179,179,179,179,179,179}

    Returns: 6

  66. {60,60,934,60,60,60,934,934,934,934,60,60,934,60,60,934,934,60,934,60,60,60,934,60,60,60,934}

    Returns: 6

  67. {18,284,384,384,18,384,384,18,18,284,384,384,384,18,18,384,384,284,18,18,284,18,18,18,18,18,284}

    Returns: 6

  68. {851,658,344,851,209,115,209,209,851,851,115,344,115,344,115,658,851,344,115,115,851,658,658,209,115,851,851}

    Returns: 6

  69. {248,796,280,956,280,782,782,280,466,280,796,496,796,66,248,782,796,782,248,248,782,796,782,956,782,248,782}

    Returns: 5

  70. {498,962,742,624,76,114,897,827,450,839,153,23,543,237,375,914,241,852,217,784,343,36,871,481,406,646,156}

    Returns: 0

  71. {764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764,764}

    Returns: 12

  72. {499,499,499,447,499,499,447,447,499,447,447,499,499,499,499,447,447,447,499,499,499,447,447,447,447,447,447,447,447,499,499,447,447,499,447,499,499,499,499,447,499,447,499,499,447,447,447,447,447,499}

    Returns: 12

  73. {472,758,758,472,875,875,472,875,472,758,758,875,875,472,472,758,472,758,758,472,758,758,472,472,875,472,472,758,472,758,758,875,758,758,875,875,472,875,758,875,758,875,758,875,875,875,472,472,875,758}

    Returns: 12

  74. {352,237,402,757,352,757,402,237,237,237,14,757,352,402,14,757,402,14,14,237,757,402,237,237,757,352,352,402,402,402,237,352,402,352,237,757,237,757,352,402,14,237,757,237,352,14,237,237,237,402}

    Returns: 10

  75. {80,435,743,435,100,683,683,683,771,406,572,771,743,821,821,743,406,406,100,743,80,821,435,100,572,406,572,771,572,771,771,406,821,406,382,572,771,100,771,80,80,821,80,743,683,743,572,771,382,572}

    Returns: 9

  76. {427,952,747,881,396,695,468,553,520,582,902,338,66,83,870,406,62,902,642,613,640,72,468,452,902,396,642,695,395,154,870,154,870,478,478,553,981,427,840,964,330,406,553,72,981,986,395,636,395,997}

    Returns: 0

  77. {334,334,334,334,334}

    Returns: 1

  78. {529,802,802,529,802}

    Returns: 0

  79. {192,296,896,896,296}

    Returns: 0

  80. {216,84,576,84,84}

    Returns: 0

  81. {915,45,417,896,767}

    Returns: 0

  82. {880,335,630,625,408}

    Returns: 0

  83. {833,833,833,833,833,833,833,833,833,833,833,833,833,833,833,833,833,833,833,833,833,833,833,833}

    Returns: 6

  84. {782,782,184,184,782,184,782,184,782,782,184,184,782,184,782,782,782,782,184,782,782,782,184,184}

    Returns: 5

  85. {498,266,705,498,705,705,266,705,266,266,705,705,705,266,705,705,498,266,498,266,705,705,705,705}

    Returns: 5

  86. {492,24,162,865,492,162,924,924,24,162,492,492,162,492,924,162,24,162,24,162,492,162,162,924}

    Returns: 5

  87. {30,30,658,821,71,73,511,71,73,195,30,658,73,27,511,796,71,511,30,30,821,821,912,73}

    Returns: 2

  88. {493,37,225,225,86,183,834,579,653,493,66,994,998,878,926,654,601,834,579,926,335,139,998,926}

    Returns: 0

  89. {410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410,410}

    Returns: 8

  90. {561,273,273,561,561,561,273,561,273,273,561,561,561,561,273,273,273,273,561,561,273,273,561,561,273,273,561,273,273,561,561,273,561,561}

    Returns: 8

  91. {311,311,311,324,311,324,346,346,324,311,346,346,311,324,346,346,324,324,311,311,311,346,311,311,346,311,324,346,311,311,311,311,324,311}

    Returns: 8

  92. {609,611,957,957,611,485,957,957,485,957,485,611,609,611,957,957,957,611,957,611,180,180,957,485,180,180,485,485,180,611,611,957,180,611}

    Returns: 6

  93. {506,57,50,50,50,50,57,506,39,607,887,871,39,271,506,871,39,607,891,871,57,50,607,871,607,57,607,50,50,39,39,50,607,891}

    Returns: 6

  94. {819,296,950,243,568,243,220,384,370,909,90,442,220,375,90,375,403,909,442,243,431,98,900,296,576,220,764,429,3,747,927,155,851,40}

    Returns: 0

  95. {508,508,508,508,508,508}

    Returns: 1

  96. {292,751,292,292,292,751}

    Returns: 1

  97. {592,592,732,732,886,886}

    Returns: 0

  98. {662,662,911,503,833,833}

    Returns: 0

  99. {182,922,164,182,231,164}

    Returns: 0

  100. {133,322,225,906,760,937}

    Returns: 0

  101. {648,648,648,648,648,648,648,648,648,648,648}

    Returns: 2

  102. {647,647,33,647,647,647,33,33,33,33,647}

    Returns: 2

  103. {623,623,623,623,623,321,321,819,623,623,623}

    Returns: 2

  104. {858,897,283,806,241,241,806,806,283,283,806}

    Returns: 1

  105. {767,675,219,144,79,144,697,631,144,388,328}

    Returns: 0

  106. {589,663,42,865,745,961,628,864,357,318,42}

    Returns: 0

  107. {58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58,58}

    Returns: 4

  108. {75,75,477,75,75,75,75,75,477,477,477,477,477,477,477,477,75}

    Returns: 4

  109. {748,748,748,474,1000,748,1000,474,748,748,748,474,474,474,474,748,1000}

    Returns: 3

  110. {414,941,414,414,292,627,292,627,627,414,627,941,708,414,292,414,292}

    Returns: 3

  111. {689,953,953,461,135,897,135,580,624,461,240,689,953,135,897,689,231}

    Returns: 0

  112. {245,620,529,641,177,26,115,987,523,402,925,159,302,620,84,987,838}

    Returns: 0

  113. {302,302,302,302,302,302,302,302,302,302,302,302,302,302}

    Returns: 3

  114. {321,375,375,321,321,375,321,321,321,321,375,321,375,321}

    Returns: 3

  115. {959,959,174,959,959,174,174,174,174,959,959,959,959,174}

    Returns: 3

  116. {985,490,775,490,985,985,490,985,490,985,269,394,775,394}

    Returns: 2

  117. {625,625,472,472,455,98,748,988,840,840,98,472,98,12}

    Returns: 0

  118. {797,569,577,183,942,893,301,577,984,364,561,382,273,830}

    Returns: 0

  119. {1,1,1,2,1,1,1,3,1,1,1}

    Returns: 2

  120. {2,2,4,4,8,8}

    Returns: 0

    You are also not allowed to break the sticks.

  121. {3, 1, 4, 4, 4, 10, 10, 10, 10 }

    Returns: 1

  122. {1000, 1000, 1000, 1000 }

    Returns: 1

  123. {88, 1, 2, 9, 4, 10, 10, 10, 10 }

    Returns: 1

  124. {1000, 1000, 1000, 1000, 1, 1, 1, 1 }

    Returns: 2

  125. {1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 2

  126. {4, 4, 4, 4 }

    Returns: 1

  127. {2, 2, 4, 4, 8, 8 }

    Returns: 0

  128. {7, 1, 1, 1, 1 }

    Returns: 1

  129. {10 }

    Returns: 0

  130. {1000, 1000, 1000, 1000, 1000 }

    Returns: 1

  131. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 3

  132. {1000, 1000, 2, 2, 1000, 1000, 2 }

    Returns: 1

  133. {900, 900, 900, 900, 1, 2, 3 }

    Returns: 1

  134. {1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    Returns: 2

  135. {1000, 1000 }

    Returns: 0

  136. {1, 1, 1, 1, 2, 2, 2, 2 }

    Returns: 2

  137. {1, 1, 1, 1 }

    Returns: 1

  138. {1000, 1, 1, 1, 1 }

    Returns: 1

  139. {900, 900, 900, 900 }

    Returns: 1

  140. {1, 1, 1, 1, 1, 1 }

    Returns: 1

  141. {500, 500, 500, 500 }

    Returns: 1

  142. {1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1 }

    Returns: 2

  143. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 3

  144. {1, 1, 2, 2, 1, 1, 2 }

    Returns: 1

  145. {1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    Returns: 2

  146. {1000, 1000, 1000, 1000, 999, 1, 2 }

    Returns: 1

  147. {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: 12

  148. {2, 2, 1, 1, 1, 1, 2, 2 }

    Returns: 2

  149. {400, 400, 400, 400 }

    Returns: 1

  150. {1, 1000, 1000, 1000 }

    Returns: 0

  151. {1, 1, 1, 1, 3, 3, 3, 3, 5, 5, 5, 5 }

    Returns: 3

  152. {1000, 999, 122, 122, 122, 122 }

    Returns: 1

  153. {1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    Returns: 1

  154. {1, 1, 2, 2, 1, 1, 2, 2 }

    Returns: 2

  155. {10, 10, 19, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 19, 19, 19, 19, 19, 19 }

    Returns: 4

  156. {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: 12

  157. {1, 1, 1, 1, 1, 1, 1 }

    Returns: 1

  158. {1000, 1000, 1000, 1000, 999, 999, 999 }

    Returns: 1

  159. {1, 1, 1, 1, 1 }

    Returns: 1

  160. {4, 4, 4, 4, 4, 4, 4 }

    Returns: 1

  161. {100, 100, 100, 100 }

    Returns: 1

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: