CSES- Missing coin Sum

help
1

I am trying to solve this CSES problem. Can anybody help.
CSES - Missing Coin Sum

6 Likes
2

This would help

Find the smallest positive integer value that cannot be represented as sum of any subset of a given array - GeeksforGeeks

11 Likes
3 
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
4

U r genius man!!