Smallest Non-Representable Number

Given an array of positive integers, determine the smallest positive integer that is not present in the array and cannot be represented as the sum of any subset of the array. In mathematical terms, find the smallest value \(x\) such that it is impossible to form \(x\) using some subset of the given integers.

The key observation is to sort the array and maintain a running sum \(res\). Initially, \(res = 1\). For each number \(a_i\) in the sorted array, if \(a_i > res\), then the current \(res\) is the answer. Otherwise, update \(res = res + a_i\). This greedy approach ensures that all numbers less than \(res\) can be formed by some subset of the processed elements.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated positive integers.

outputFormat

Output via standard output (stdout) a single integer — the smallest positive integer that cannot be represented as the sum of any subset of the array.

6
1 2 6 10 11 15

4