# Given an array of positive integers representing the values of coins
# in your possession, write a function that returns the minimum amount
# of change (the minimum sum of money) that you cannot create. The given
# coins can have any positive integer value and aren't necessarily unique
# (i.e., you can have multiple coins of the same value).

# For example, if you're given coins = [1, 2, 5], the minimum amount of change
# that you can't create is 4. If you're given no coins, the minimum amount of
# change that you can't create is 1.
# Sample Input
# coins = [5, 7, 1, 1, 2, 3, 22]
# Sample Output
# 20

# Solution 1. Time complexity: O(n*logn) for sorting. Space complexity: O(1)
# Keep a running sum of the available change after sorting the array. If at
# any point we have a coin that exceeds the current change, that means we cannot
# use that coin to make (change + 1) amount. Alternatively, if none of the coins
# satisfy this condition, then the next non-constructible change is (change + 1)
# where change is the total of all coins.
def non_constructible_change(coins):
	coins.sort()
	change = 0
	for coin in coins:
		if coin > change + 1:
			break
		change += coin
	return change + 1

print(non_constructible_change([5, 7, 1, 1, 2, 3, 22]))
print(non_constructible_change([1, 1, 1, 1, 1]))
print(non_constructible_change([1, 5, 1, 1, 1, 10, 15, 20, 100]))