All submissions for this problem are available.
Alan is a young, money making minded teenage chap who wants to make a few quick bucks, so he takes to lotteries, but his luck seems to be eluding him at each corner. So he turned to Steve, a numerologist, Steve gave him N natural numbers and asked him to buy a specific numbered lottery ticket . The number on the ticket which can win a lottery for Alan should be the least integer value that cannot be obtained from the sum of all the elements of any set formed from the given N natural numbers. The problem is that Alan is very bad at math, so he has turned to you for help. Help Alan in finding the correct card number, which can win a lottery for him.
- First line contains T denoting the number of test cases.
- Next T lines contains N the numbers given by Steve.
- Next line contains N space separated natural numbers (A, A, ..., A[N]).
- Print the number on the ticket which wins lottery for Alan.
- 1 <= T <= 1000
- 1 <= N <= 100000
- 1 <= A[i] <= 100000
Input: 2 2 2 8 2 1 2 Output: 1 4
Case 1 : 1 cannot be generated from any sum of the set.
Case 2 : Out of the numbers 1 and 2 can be formed from the numbers given. For 3, is generated using 1 and 2. 4 is the least number that cannot be generated from any sum of the set
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions