Statistics

Problem Statement for "NumbersChallenge"

Problem Statement

Your friend Lucas gave you a sequence S of positive integers.


For a while, you two played a simple game with S: Lucas would pick a number, and you had to select some elements of S such that the sum of all numbers you selected is the number chosen by Lucas. For example, if S={2,1,2,7} and Lucas chose the number 11, you would answer that 2+2+7 = 11.


Lucas now wants to trick you by choosing a number X such that there will be no valid answer. For example, if S={2,1,2,7}, it is not possible to select elements of S that sum up to 6.


You are given the int[] S. Find the smallest positive integer X that cannot be obtained as the sum of some (possibly all) elements of S.


Definition

Class:
NumbersChallenge
Method:
MinNumber
Parameters:
int[]
Returns:
int
Method signature:
int MinNumber(int[] S)
(be sure your method is public)

Constraints

  • S will contain between 1 and 20 elements, inclusive.
  • Each element of S will be between 1 and 100,000, inclusive.

Examples

  1. {5, 1, 2}

    Returns: 4

    These are all the positive integers that can be obtained: 1, 2, 3, 5, 6, 7, and 8. (We can obtain 3 as 1+2, 6 as 1+5, 7 as 2+5, and 8 as 1+2+5.) The smallest positive integer not present in the above list is 4.

  2. {1, 3, 26, 14, 28, 15, 3, 3, 35, 1, 2, 212, 30, 126}

    Returns: 500

  3. {6, 3, 33, 158, 100, 331, 4, 66, 132, 512, 2, 1, 1, 12, 3, 1, 1257, 1, 6}

    Returns: 2630

  4. {2, 12, 137, 3, 1, 8, 60, 25, 184, 1, 23, 6, 276}

    Returns: 739

  5. {53, 29, 1, 82, 125, 7, 1, 3, 29, 2, 2, 5, 7, 44, 1, 160, 3, 50, 1, 7}

    Returns: 613

  6. {2048, 256, 16384, 2, 1024, 8, 16, 32, 1, 512, 128, 4, 64, 4096, 8192}

    Returns: 32768

  7. {1024, 8, 256, 4, 2048, 4096, 64, 2, 8192, 16, 1, 512, 128, 32}

    Returns: 16384

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

    Returns: 256

  9. {256, 1024, 16, 2, 4, 8, 64, 128, 1, 32, 4096, 2048, 512}

    Returns: 8192

  10. {64, 8192, 99932, 512, 65536, 1024, 2, 2048, 4, 4096, 16384, 8, 15919, 256, 32, 1, 32768, 128, 16}

    Returns: 246923

  11. {2, 1, 4}

    Returns: 8

    We can obtain each of the sums from 1 to 7, inclusive. The smallest impossible sum is 8.

  12. {4, 1, 2}

    Returns: 8

  13. {2, 1, 2, 7}

    Returns: 6

    The example given in the problem statement.

  14. {46148, 4, 2, 58416, 1, 80011}

    Returns: 8

  15. {1, 14225, 1, 1, 1, 59962, 93481, 71261, 14875, 4}

    Returns: 9

  16. {19755, 72594, 48311, 98571, 1, 1, 1, 2, 1, 9408}

    Returns: 7

  17. {1, 4545, 99004, 17031, 60877, 9816, 3, 8, 14, 20698, 5, 1}

    Returns: 33

  18. {79150, 8, 8561, 51120, 29, 47009, 97589, 2, 58299, 1, 49825, 2, 4, 83988, 11752, 33509, 2, 57, 11}

    Returns: 117

  19. {1, 32667, 84703, 1, 58792}

    Returns: 3

  20. {9380, 1, 50305}

    Returns: 2

  21. {4, 44682, 79954, 53565, 98353, 1, 26006, 2, 2, 11421, 2}

    Returns: 12

  22. {84772, 50764, 47506, 3, 5, 5511, 23417, 2, 1}

    Returns: 12

  23. {2, 10, 9, 3, 4, 6}

    Returns: 1

  24. {1, 40560, 1, 928}

    Returns: 3

  25. {1, 1}

    Returns: 3

  26. {29, 55, 1, 85684, 85684, 85684, 3, 85684, 8, 33, 1, 85684, 1, 85684, 85684, 14, 85684, 1}

    Returns: 147

  27. {3, 2, 14, 9, 1, 1, 47, 2, 2, 32}

    Returns: 114

  28. {55064, 55064, 55064, 7, 3, 1, 1, 55064, 55064, 4, 55064, 55064, 3, 55064, 1, 3, 6, 55064, 12}

    Returns: 42

  29. {1, 92050, 1, 92050, 92050, 1, 6, 92050, 92050, 14, 1, 4, 92050, 92050, 33, 11, 92050, 92050, 3}

    Returns: 76

  30. {7, 44741, 44741, 1, 1, 44741, 44741, 44741, 12, 3, 12, 44741, 1, 44741, 3, 44741, 2, 8}

    Returns: 51

  31. {1}

    Returns: 2

  32. {2, 1}

    Returns: 4

  33. {1, 2, 1, 1}

    Returns: 6

  34. {1, 1, 1, 1, 1}

    Returns: 6

  35. {10, 5, 10, 1, 1, 4, 1, 20}

    Returns: 53

  36. {17183, 1, 50885, 20797, 10, 20, 43, 37249, 48449, 75677, 54065, 8, 5, 61635, 1, 1, 71149, 81500, 3, 2}

    Returns: 95

  37. {47222, 1, 62178, 3, 5, 5, 65487, 71317, 17, 2, 31048, 5, 8, 41824, 57562, 75483, 41, 2, 70955, 19211}

    Returns: 90

  38. {86151, 61450, 18234, 9, 90468, 17, 69809, 3, 88415, 23, 24, 60312, 35320, 1, 6, 7067, 1, 79865, 60, 5}

    Returns: 150

  39. {74271, 84843, 23652, 38973, 7, 3, 6, 1, 88876, 33265, 9, 20603, 33, 40913, 2, 4806, 49045, 10, 2, 29}

    Returns: 103

  40. {75105, 1, 2, 2, 87062, 40717, 24, 2, 1, 63328, 3, 1, 95196, 77310, 19266, 21865, 15, 41093, 2, 85003}

    Returns: 54

  41. {2, 20047, 98042, 5319, 1598, 6868, 1, 47301, 27692, 87, 2, 94767, 50758, 7, 16, 30, 53, 7, 56747, 3}

    Returns: 209

  42. {2, 39688, 1, 64279, 1, 26989, 14, 52436, 37830, 17915, 29382, 5, 9454, 3, 2, 3, 93588, 4, 2, 32461}

    Returns: 38

  43. {15347, 83708, 22160, 60267, 6, 5, 2, 11, 83508, 31485, 1, 67618, 1, 84047, 60461, 6, 41964, 3, 11, 24}

    Returns: 71

  44. {91671, 1, 58769, 63024, 14317, 95285, 1, 16, 1, 1, 4, 89237, 5, 42303, 1, 69789, 60660, 1, 8943, 6}

    Returns: 38

  45. {2, 173, 3, 2, 194, 92, 23, 41, 475, 1, 11, 2, 1, 71}

    Returns: 1092

  46. {1, 70560, 1, 7, 70560, 55747, 12370, 28273, 8, 18499, 1, 2, 2, 7, 79906, 74838, 44507, 28585, 1, 12}

    Returns: 43

  47. {16, 14, 14, 26732, 1, 2989, 190, 96410, 149, 34, 2, 362, 705, 63, 5239, 4, 488, 407, 6, 37}

    Returns: 2493

  48. {54, 2, 24, 1, 11, 1, 42, 44831, 3, 35, 115, 18564, 125, 1, 128, 509, 13165, 74, 8, 18962}

    Returns: 1134

  49. {2, 10, 1, 354, 40, 1, 1, 5, 16, 96280, 4207, 59995, 71, 121, 3, 130, 25, 2, 52827, 2}

    Returns: 785

  50. {42318, 3, 14, 1, 21, 71075, 88014, 2, 86718, 4, 14, 106, 1, 164, 1, 43, 51, 18, 55, 5}

    Returns: 504

  51. {94512, 2, 87654, 81316, 6, 5, 6, 37151, 6, 139, 1, 36, 307, 1, 377, 101, 8, 37, 58, 1}

    Returns: 1092

  52. {7, 34, 75798, 17, 61124, 62989, 161, 114, 450, 1, 83086, 1, 11, 22, 2, 41, 70, 11, 2, 3}

    Returns: 948

  53. {10, 86, 1, 1, 42, 57389, 85, 2, 1, 11754, 5, 363, 1, 5, 192, 13, 1, 13745, 40861, 7}

    Returns: 816

  54. {28, 4, 48463, 23, 32, 183, 202, 17, 27495, 9, 1, 46, 11935, 94762, 498, 1, 74, 1, 1, 3}

    Returns: 1124

  55. {78225, 29, 2, 145, 15, 141, 2, 12, 36, 82, 85390, 1, 90765, 3, 7, 88847, 1, 1, 4, 451}

    Returns: 933

  56. {2, 3, 1}

    Returns: 7

  57. {217, 76694, 1, 13546, 319, 20, 1, 1, 93155, 3, 22, 13, 25, 28, 180, 7, 78, 27008, 714, 23}

    Returns: 1653

  58. {16, 69, 2, 91, 452, 66170, 240, 23, 8, 909, 18, 1462, 8, 32, 1, 3257, 60, 4, 5006, 38613}

    Returns: 11659

  59. {738, 27, 97092, 79963, 35, 4, 70, 36, 2260, 829, 2, 242, 3, 120, 38, 10, 1, 6, 157, 68}

    Returns: 4647

  60. {1, 17, 6, 276, 99, 1, 87009, 1, 77, 2, 1497, 24, 1094, 11, 634, 74132, 2, 211, 64, 97}

    Returns: 4115

  61. {7, 185, 1, 6, 16, 64, 1, 3, 15, 85464, 26, 843, 143, 257, 71886, 33, 187, 1, 208, 1}

    Returns: 1998

  62. {11, 6, 688, 39130, 85, 243, 15, 1, 521, 1, 1, 1, 1, 39677, 30, 41, 28, 177, 21, 41}

    Returns: 1913

  63. {2, 91670, 7, 2, 2, 34, 301, 1, 2, 48, 451, 12, 62039, 16, 38, 14, 45, 227, 2, 33}

    Returns: 1238

  64. {134, 31, 10, 45, 3, 11, 7, 346, 68, 1, 89746, 513, 12, 1, 60, 1, 5, 40, 69615, 27}

    Returns: 1316

  65. {55, 2, 78, 20, 382, 121, 142, 19, 2, 10, 1, 9, 64055, 1, 288, 2, 4, 90207, 54, 7}

    Returns: 1198

  66. {115, 3, 1396, 1, 369, 15, 3, 1, 97455, 6, 5290, 1, 30, 91, 12, 955, 191, 43, 67, 90}

    Returns: 3390

  67. {28, 9, 5, 67, 4, 2, 1, 21, 34, 95, 52}

    Returns: 319

  68. {27, 101, 36, 485, 1, 4, 1, 14, 1, 29, 2, 86154, 325, 17, 127, 3, 208, 481, 76223, 2}

    Returns: 1865

  69. {12, 9, 73, 64, 38525, 3386, 5, 459, 1662, 1, 29, 843, 1, 77582, 306, 204, 2, 188, 18, 6}

    Returns: 7269

  70. {192, 3, 720, 2, 1, 67188, 3, 577, 85, 26, 1, 9, 60, 2153, 128, 48, 18, 288, 63746, 2146}

    Returns: 6461

  71. {595, 13, 74, 1832, 5041, 4355, 15611, 953, 187, 4, 3, 69609, 31, 9, 1, 9, 1, 202, 72, 585}

    Returns: 13968

  72. {1887, 1, 11, 93621, 1, 331, 886, 88239, 5, 49, 130, 5, 273, 2, 9, 31, 1398, 34, 112, 497}

    Returns: 5663

  73. {21, 259, 1, 35, 225, 812, 1, 1, 58544, 361, 14, 82, 58, 1516, 5, 17494, 541, 6, 4, 10}

    Returns: 3953

  74. {3, 7, 1, 1, 142, 8795, 38, 25, 85, 57, 5, 98120, 21, 805, 1208, 358, 318, 537, 10, 3}

    Returns: 3625

  75. {115, 54, 2, 1210, 405, 8246, 5, 46, 1, 18, 9278, 12, 8, 1, 462, 4, 3, 1034, 173, 77}

    Returns: 3631

  76. {86023, 1039, 3, 66, 895, 73247, 29, 2, 439, 4, 1608, 366, 11, 126, 41, 84, 3003, 7, 1, 5}

    Returns: 7730

  77. {42, 95, 1, 6, 406, 84422, 2745, 10, 385, 1441, 10, 913, 3, 609, 15, 142, 1, 39, 23206, 63}

    Returns: 6927

  78. {1, 1, 94, 7, 172, 354, 1, 8, 34, 561, 1606, 2407, 1, 12, 4, 9, 204, 19, 449, 3}

    Returns: 5948

  79. {16, 687, 3, 1, 5, 65822, 3486, 7, 1, 2, 728, 1092, 1, 85, 38, 84, 256, 257, 11, 2}

    Returns: 3277

  80. {990, 31, 15860, 1984, 1, 7931, 6, 1, 1, 248, 62, 126, 40882, 5, 498, 3963, 1, 1, 16, 90687}

    Returns: 31726

  81. {56138, 1, 6, 7, 1, 225, 1, 31, 12, 14372, 34357, 7188, 56, 451, 109, 1, 3592, 1796, 1, 898}

    Returns: 28749

  82. {62031, 9, 1, 82308, 401, 804, 99, 10, 50, 6420, 3, 1601, 3210, 1, 201, 1, 1, 26, 1, 12836}

    Returns: 25676

  83. {5387, 12, 2, 674, 39, 3, 2693, 1, 58558, 169, 85, 98182, 1, 21547, 21, 1, 10775, 5, 1347, 340}

    Returns: 43103

  84. {3245, 52475, 811, 201, 410, 54813, 1623, 24, 3, 1, 12984, 51, 5, 1, 1, 25971, 102, 5, 6490, 15}

    Returns: 51944

  85. {3763, 7527, 31, 12, 474, 1, 234, 7, 940, 3, 116, 4, 3, 1881, 15056, 54186, 1, 31835, 1, 60}

    Returns: 30115

  86. {149, 1, 17, 1, 2344, 4, 1172, 1, 37249, 2, 5, 1, 73, 1, 8, 99615, 586, 4691, 294, 35}

    Returns: 9386

  87. {1, 11, 700, 352, 3, 4, 70288, 3, 24, 2796, 174, 71018, 85, 1, 1, 5600, 11191, 1, 1400, 43}

    Returns: 22391

  88. {66766, 5832, 363, 46, 1, 731, 1, 185, 90, 1, 1, 4, 1, 62245, 13, 2917, 1456, 6, 11661, 20}

    Returns: 23330

  89. {14, 4, 9, 1, 1, 9, 1, 3}

    Returns: 43

  90. {883, 66392, 3531, 28257, 1, 14131, 57, 1, 25, 88474, 4, 1, 110, 6, 1769, 220, 442, 7064, 7, 13}

    Returns: 56523

  91. {883, 66392, 3531, 28257, 1, 14131, 57, 1, 25, 88474, 4, 1, 110, 6, 1769, 220, 442, 7064, 7, 13 }

    Returns: 56523

  92. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536 }

    Returns: 131072

  93. {10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000 }

    Returns: 1

  94. {1, 2 }

    Returns: 4

  95. {1, 10, 100, 1000, 10000, 100000, 100000, 100000, 99999, 99997, 99999, 99993, 99995, 99996, 99992, 39999, 99991, 99998, 100000, 999 }

    Returns: 2

  96. {5 }

    Returns: 1

  97. {2, 1, 4 }

    Returns: 8

  98. {5, 3, 2 }

    Returns: 1

  99. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

    Returns: 211

  100. {2 }

    Returns: 1

  101. {7 }

    Returns: 1

  102. {5, 4, 2 }

    Returns: 1

  103. {94512, 2, 87654, 81316, 6, 5, 6, 37151, 6, 139, 1, 36, 307, 1, 377, 101, 8, 37, 58, 1 }

    Returns: 1092

  104. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 100000 }

    Returns: 231072

  105. {5, 2 }

    Returns: 1

  106. {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 65536, 65537, 99999, 99988 }

    Returns: 1

  107. {2, 100, 4 }

    Returns: 1

  108. {1 }

    Returns: 2

  109. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 99941, 99967, 99934 }

    Returns: 430914

  110. {2, 3, 4 }

    Returns: 1

  111. {5, 1, 2 }

    Returns: 4

  112. {1, 2, 3, 7, 8, 9 }

    Returns: 31

  113. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 99999 }

    Returns: 231071

  114. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 65536, 65536, 65536 }

    Returns: 327680

  115. {5, 6, 7 }

    Returns: 1

  116. {1, 2, 4 }

    Returns: 8

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: