Smallest Impossible Sum

Difficulty: 1600 3000 ms 128 MB

greedy sorting

Using each coin at most once, sums are formed as subsets of the coins. Print the smallest positive integer that is NOT representable.

Input: the first line has N; the second line has N positive coin values.

Output: the smallest positive unreachable subset sum.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ a_i ≤ 10⁹

Sample Tests

4
1 1 3 5

11

2
2 3

1

Read the Editorial