NumbersChallenge
SRM 621 · 2013-12-22 · by ivan_metelsky
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
Constraints
- S will contain between 1 and 20 elements, inclusive.
- Each element of S will be between 1 and 100,000, inclusive.
{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.
{1, 3, 26, 14, 28, 15, 3, 3, 35, 1, 2, 212, 30, 126}
Returns: 500
{6, 3, 33, 158, 100, 331, 4, 66, 132, 512, 2, 1, 1, 12, 3, 1, 1257, 1, 6}
Returns: 2630
{2, 12, 137, 3, 1, 8, 60, 25, 184, 1, 23, 6, 276}
Returns: 739
{53, 29, 1, 82, 125, 7, 1, 3, 29, 2, 2, 5, 7, 44, 1, 160, 3, 50, 1, 7}
Returns: 613
{2, 1, 4}
Returns: 8
We can obtain each of the sums from 1 to 7, inclusive. The smallest impossible sum is 8.
{2, 1, 2, 7}
Returns: 6
The example given in the problem statement.
Submissions are judged against all 116 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NumbersChallenge with a public method int MinNumber(vector<int> S) · 116 test cases · 2 s / 256 MB per case