Skip to content
Hiring process8 levels
  1. 1 IQ Test
  2. 2 Additional Online Test (If Required)
  3. 3 Office Interview with Hiring Manager
  4. 4 Unpaid Test Task (Motivation Check)
  5. 5 Paid Test Task and Follow-Up Interview
  6. 6 Iterative Paid Test Tasks
  7. 7 Office Verification
  8. 8 Final Interview with the Founder

Problems > Smallest Impossible Sum

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 ≤ 105
  • 1 ≤ ai ≤ 109

Sample Tests

Input 1
4
1 1 3 5
Output 1
11
Input 2
2
2 3
Output 2
1

Discussion (opens after you solve — no spoilers before)

No comments yet — solve the problem to start the discussion.

Submit Your Solution

Log in or create a free account to run and submit code.
Ctrl+Enter submit · Ctrl+Space autocomplete · F11 fullscreen