§ Smallest positive natural which can't be represented as sum of any subset of a set of naturals

we're given a set of naturals S{xi}S \equiv \{ x_i \} and we want to find nmin{sum(T):TS}n \equiv \min \{ sum(T): T \subseteq S \}, the smallest number that can't be written as a sum of elements from SS.

§ By observation

  • Key observation: If we sort the set SS as s[1]s[2]s[n]s[1] \leq s[2] \leq \dots \leq s[n], then we must have s[1]=1s[1] = 1. For if not, then 11 is the smallest nmber which cannot be written as a sum of elements.
  • Next, if we think about the second number, it must be s[2]=2s[2] = 2. If not, we return 22 as the answer.
  • The third number s[3]s[3] can be 33. Interestingly, it can also be 44, since we can write 3=1+23 = 1 + 2, so we can skip 33as an input.
  • What about s[4]s[4]? If we had [123][1 \leq 2 \leq 3] so far, then see that we can represent all numbers upto 66. If we have [124][1 \leq 2 \leq 4] so far, then we can represent all numbers upto 77. Is it always true that given a "satisfactory" sorted array AA (to be defined recursively), we can always build numbers upto A\sum A?
  • The answer is yes. Suppose the array AA can represent numbers upto A\sum A. Let's now append rsum(A)+1r \equiv sum(A)+1 into AA. ( rr for result). Define B := append(A, r). We claim we can represent numbers [1(r+A)][1 \dots (r+\sum A)] using numbers from BB. By induction hypothesis on A. We can represent [1A][1 \dots \sum A ] from AA. We've added r=A+1r = \sum A + 1 to this array. Since we can build numbers [1A][1\dots \sum A] from AA, we can add rr to this to build the range [r+1r+A][r+1 \dots r + \sum A]. In total, by not choosing rr, we build the segment [1A][1 \dots \sum A ] and by choosing rr we build the segment [A+1A+r][\sum A + 1 \dots \sum A + r]giving us the full segment [1A+r][1 \dots \sum A + r].

§ Take 2: code

  • Input processing:
void main() {
  int n;
  cin >> n;
  vector<ll> xs(n);
  for (ll i = 0; i < n; ++i) {
    cin >> xs[i];
  • Sort to order array
  sort(xs.begin(), xs.end());
  • Next define r as max sum seen so far.
  ll r = 0; // Σ_i=0^n xs[i]
  • We can represent number [0r][0\dots r] What can xs[i]xs[i] be? If it is greater than (r+1)(r+1), then we have found a hole. If xs[i]=r+1xs[i] = r+1, then we can already represent [0r][0\dots r]. We now have (r+1)(r+1). By using the previous numbers, we can represent the sums (r+1)+[0r](r+1) + [0 \dots r], which is equal to [r+12r+1][r+1 \dots 2r+1].
  • More generally, if xs[i]<r+1xs[i] < r+1, we can represent [0r];[xs[i]+0,xs[i]+r][0 \dots r]; [xs[i]+0, xs[i]+r].
  • The condition that this will not leave a gap between rr and xs[i]xs[i] is to say that xs[i]+0(r+1)xs[i]+0 \leq (r+1).
  for (ll i = 0; i < n; ++i) {
    if (xs[i] <= r+1) {
      // xs[i] can represent r+1.
      // We can already represent [0..r]
      // By adding, we can represent [0..r] + (xs[i]) = [xs[i]..r+xs[i]]
      // Since xs[i] <= r+1, [xs[i]..r+xs[i]] <= [r+1, 2r+1].
      // In total, we can represent [0..r] (not using xs[i]) and [<=r+1, <=2r+1]
      // (by using xs[i]) So we can can be sure we won't miss numbers when going
      // from [1..r] to [xs[i]<=r+1...] The largest number we can represent is
      // [xs[i]+r].
      r += xs[i]; // max number we can represent is previous max plus current
    } else {
      // xs[i] > r+1. We have a gap at r+1
      cout << r + 1 << "\n";
  cout << r + 1 << "\n";