Statistics

Problem Statement for "MislabeledWeights"

Problem Statement

You are given a balance scale to weigh some items. Unfortunately the weights you use as counterbalances are not accurate. Some of them may be marked incorrectly - either 1 gram too heavy or one gram too light. (Some may be marked correctly.)

You are given a int[] weights representing the set of weights you have. The i-th of your weights is marked by weights[i] grams. The subset of your weights is called good if it's possible that all the real weights in it sum exactly to testWeight. Find the good subset with the minimum possible number of weights and return the number of weights in it. If there is no good subset of weights, your method should return -1.

Definition

Class:
MislabeledWeights
Method:
fewest
Parameters:
int[], int
Returns:
int
Method signature:
int fewest(int[] weights, int testWeight)
(be sure your method is public)

Notes

  • A weight labeled '1 gram' (represented as the integer 1 in the int[] of weights) can only be 1 or 2 grams. All other weights can be plus or minus 1 gram of their actual labeled weight.
  • There may be duplicates in the weights but you may only use each element at most once.

Constraints

  • weights will contain between 1 and 10 elements, inclusive.
  • Each element of weights will be between 1 and 1000, inclusive.
  • testWeight will be between 1 and 10000, inclusive.

Examples

  1. {1,1,1}

    6

    Returns: 3

    The subset of all weights is the only good one. If all the real weights are 2 grams, then they sum up to 6 grams.

  2. {1,1,1}

    7

    Returns: -1

    Even if each weight was actually 2 grams, there would still be no way for them to sum to 7 grams.

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

    7

    Returns: 2

    There are many good subsets. For example, {1, 5} (1 + 6 = 7 or 2 + 5 = 7), or {3, 4} (3 + 4 = 7 or 4 + 3 = 7), or {3, 5} (3 + 4 = 7 or 2 + 5 = 7), or other variants. In any case, the fewest number of weights in a good subset is 2.

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

    47

    Returns: 2

  5. {999,1000,1000,999,1000}

    3000

    Returns: 3

  6. {3,3,3,3,3,3,3,3,3,3}

    25

    Returns: 7

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

    50

    Returns: 6

  8. {1,187,243,729,561,683,81}

    841

    Returns: -1

  9. {1,20,100,200,500,1000}

    150

    Returns: -1

  10. {12,415,34,324,678,345,21,458,456}

    1445

    Returns: 5

  11. {123,234,345,456,567,678,789}

    2514

    Returns: 6

  12. {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    10000

    Returns: 10

  13. {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    9990

    Returns: 10

  14. {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    1

    Returns: -1

  15. {1,1,1,1,1,1,1,1,1,1}

    19

    Returns: 10

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

    25

    Returns: 5

  17. {1,10,20,40,80,160,320,640,1000,1000}

    234

    Returns: 4

  18. {1000,500,250,125,37,12,6,1}

    2000

    Returns: -1

  19. {1000,500,250,125,37,12,6,1}

    1930

    Returns: 6

  20. {1000,500,250,125,37,12,6,1}

    1150

    Returns: -1

  21. {1, 243, 81, 683}

    841

    Returns: -1

    682 + 242 - 1 - 82 = 841 can't put 1 or 82 on the "other" side.

  22. {150,515,683,228,903,627,877,680}

    4037

    Returns: 7

  23. {888,381,981,143,652,404,620,355}

    4422

    Returns: 8

  24. {575,216,143,188,667,6}

    1131

    Returns: 5

  25. {738,185}

    922

    Returns: 2

  26. {879,281,819,898,663,808}

    3531

    Returns: 5

  27. {715,639}

    1352

    Returns: 2

  28. {60,868,727,229,441}

    1598

    Returns: 4

  29. {367,888}

    1257

    Returns: 2

  30. {434,116,806,624,938,913,731,988,247}

    5796

    Returns: 9

  31. {934,858,234,660,781,132}

    2939

    Returns: 5

  32. {135,346,647,920,194}

    2046

    Returns: 4

  33. {744,675,766,367,631,601,762,620,399}

    2505

    Returns: 4

  34. {147,321,460,9,790}

    1398

    Returns: 3

  35. {803,19,401,237}

    637

    Returns: 2

  36. {710,437}

    1149

    Returns: 2

  37. {179}

    178

    Returns: 1

  38. {326}

    7737

    Returns: -1

  39. {550}

    7912

    Returns: -1

  40. {748,129,892,819,44}

    9125

    Returns: -1

  41. {708,690,921,343,117,257}

    1998

    Returns: 4

  42. {845,200,277,705}

    6785

    Returns: -1

  43. {586,193,480,640,249,533,159}

    2487

    Returns: 5

  44. {388,897,527}

    1814

    Returns: 3

  45. {538,159,855,351,849,158,734,910,274,813}

    4667

    Returns: 7

  46. {977}

    6975

    Returns: -1

  47. {391,658,122,852,751,460,677,472,867,125}

    4136

    Returns: 7

  48. {397}

    4672

    Returns: -1

  49. {571,338,767}

    571

    Returns: 1

  50. {83,574}

    8921

    Returns: -1

  51. {954,966,629,611}

    9133

    Returns: -1

  52. {478}

    5118

    Returns: -1

  53. {121,460,959,509,682}

    1773

    Returns: 4

  54. {320,563,689,109,598,264,950,925,565}

    4058

    Returns: 7

  55. {617,373,129,247,989,93}

    2448

    Returns: 6

  56. {88,974,806}

    1867

    Returns: 3

  57. {509,181,779,742,157,800,114,414}

    3580

    Returns: 7

  58. {868,730,664}

    1599

    Returns: 2

  59. {981,981,285,782,922,477}

    2884

    Returns: 3

  60. {505,283,920,594,591,732,981}

    3734

    Returns: 5

  61. {772,482,949,475,16,386,693,617}

    3989

    Returns: 6

  62. {86,297,663,300,905,432,213}

    2896

    Returns: 7

  63. {144,484,789,446,248,984,794,36}

    3780

    Returns: 7

  64. {42,730,968,455,72,782,118}

    2267

    Returns: 4

  65. {4,767,661,826}

    2261

    Returns: 4

  66. {288,76,971,71}

    432

    Returns: 3

  67. {294,249,377,622,928,921,203,517,952}

    8304

    Returns: -1

  68. {698,213,839,719,518,711,720,404,968}

    5169

    Returns: 7

  69. {851,286,725,772,928,393}

    2252

    Returns: 4

  70. {421,704}

    1126

    Returns: 2

  71. {600,837}

    1437

    Returns: 2

  72. {411,542,608}

    1017

    Returns: 2

  73. {497,161,261,757}

    1178

    Returns: 3

  74. {504,34,770,727,639,58,196,922,644,767}

    4757

    Returns: 9

  75. {685,981,15,510,727,522,538,657,225}

    3879

    Returns: 8

  76. {521,325,380,796,481,855}

    2559

    Returns: 5

  77. {732}

    872

    Returns: -1

  78. {156,664}

    157

    Returns: 1

  79. {424,487,30,321,6,133,720,655,533,696}

    2259

    Returns: 4

  80. {78,461,529,208,642,868,367,662}

    2304

    Returns: 5

  81. {319,759,34,839}

    793

    Returns: 2

  82. {820,973}

    1795

    Returns: 2

  83. {790,77}

    868

    Returns: 2

  84. {228,802,971,462}

    2339

    Returns: -1

  85. {166,752,846,383,201,51,146,696,351,622}

    4212

    Returns: 10

  86. {725,315,658,447,919,41,552,913}

    3807

    Returns: 6

  87. {510,398,776,331,706}

    2018

    Returns: 4

  88. {54,378,401,556,589,298,469,240}

    2428

    Returns: 7

  89. {516,285,49}

    333

    Returns: 2

  90. {487,442,255,449,434,44,529,365,231,704}

    3090

    Returns: 7

  91. {960,674,940,313,193,368,441,58,553}

    4501

    Returns: 9

  92. {400,877,891}

    890

    Returns: 1

  93. {509,94,868}

    869

    Returns: 1

  94. {799,986,987}

    2884

    Returns: -1

  95. {904,678,365}

    9346

    Returns: -1

  96. {259,370,580,9,189,218}

    1623

    Returns: 6

  97. {432,311,505,337,905,727}

    3219

    Returns: 6

  98. {198,556,712,984}

    1892

    Returns: 3

  99. {598,635,328,245,813,692,647}

    2096

    Returns: 3

  100. {729,147}

    876

    Returns: 2

  101. {878,964,607,887,982}

    3712

    Returns: 4

  102. {460,344,860,418,414,504}

    2953

    Returns: -1

  103. {299,950,544,42,428,365,687,582}

    5221

    Returns: -1

  104. {943,906,89}

    1850

    Returns: 2

  105. {625,596,815,550,748}

    1371

    Returns: 2

  106. {716}

    715

    Returns: 1

  107. {90,411,805,714,184,277,80}

    2285

    Returns: 5

  108. {302,935,228,61,12,418,364,572,278,502}

    3397

    Returns: 9

  109. {262,873}

    1136

    Returns: 2

  110. {162,127}

    288

    Returns: 2

  111. {427,878,615,606,290,481,645}

    3940

    Returns: 7

  112. {380,617,517,780,310,547,387,275}

    3269

    Returns: 7

  113. {999,958,940,816,488,941,568,753,449}

    6177

    Returns: -1

  114. {28,182}

    28

    Returns: 1

  115. {166,105,526,304,734,607}

    1837

    Returns: 5

  116. {963,37,622,534}

    36

    Returns: 1

  117. {196,763,844,312,435}

    2354

    Returns: 4

  118. {361,101}

    462

    Returns: 2

  119. {870,645,878,328}

    1515

    Returns: 2

  120. {315,236,484,478,334,444,201}

    1358

    Returns: 4

  121. {125,341,723,362}

    1550

    Returns: 4

  122. {3, 3, 3 }

    1

    Returns: -1

  123. {1, 1, 1, 1 }

    8

    Returns: 4

  124. {1000, 900 }

    1900

    Returns: 2

  125. {1, 3, 4 }

    1

    Returns: 1

  126. {1, 1, 1, 100 }

    199

    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: