I am trying to solve this CSES problem. Can anybody help.

CSES - Missing Coin Sum

6 Likes

**This would help**

11 Likes

```
n = int(input())
a = sorted(list(map(int,input().split())))
currSum = 0
for i in range(n):
if currSum + 1 < a[i]:
break
currSum += a[i]
print(currSum+1)
```

Explanation:

At any index **i** in a sorted array **a**, currSum represents `sum(a[ 0...i ])`

.

We can form every possible sum from `1...currSum`

, when we are at index i. So the next possible smallest sum at index **i** can be `currSum+1`

.

We can get `currSum+1`

as the answer if and only if `a[i+1] > currSum + 1`

, otherwise we would be able to form subsets with sums from `1...(currSum + a[i+1])`

( just add a[i+1] to all subsets which give sum `1...currSum`

to get subsets giving sum `1...currSum+a[i+1]`

).

Try this on pen and paper and it will be more clear.

18 Likes

U r genius man!!