Missing Coin Sum

Explanation

Here, we are given n coins and we need to find the smallest value of the sum that cannot be created using a subset of the coins.

This can be done using a greedy algorithm. We can sort the coins in ascending order and then iterate through them. At each step, we can check if the current coin is greater than the current sum plus 1. If it is, then we have found the smallest value that cannot be created using a subset of the coins.

For example, if we have the coins [1, 2, 3, 8, 9], then we can iterate through them as follows:

• 1 is less than or equal to 0 + 1, so we can create 1 using a subset of the coins. (we increment s by 1)
• 2 is less than or equal to 1 + 1, so we can create 2 using a subset of the coins. (we increment s by 2)
• 3 is less than or equal to 3 + 1, so we can create 3 using a subset of the coins. (we increment s by 3)
• 8 is greater than 6 + 1, so we cannot create 4 using a subset of the coins. Therefore, 4 is the smallest value that cannot be created using a subset of the coins.

Code

n = int(input())
arr = sorted(list(map(int, input().split())))

s = 0
for e in arr:
    if e > s + 1:
        break
    s += e

print(s + 1)