# Non-Constructible Change
Date: 2022-05-04


##### **问题：**

给定一系列正整数，代表硬币的面值，找到无法从这些整数组连续组合成的最小值。比如 coins=\[1,2,5\], 最小不能组合成的值为4.

##### **解答：**

如果下一个整数大于前面所有值的累积和 + 1，那么就知道最小值，如果能被组合范围\[0, sum\], 下一个数据为y， 如果能构造出联系数据 sum+1 要在 \[y，sum+y\]范围内。也就是y<=sum+1<=sum+y。 由于排序数组 y>=1, 也就是满足y>sum+1。就可以找到最小组合值。

 

```
def nonConstructibleChange(coins):
    # Write your code here.
    coins.sort()
    
    currentChangeCreated = 0
    for coin in coins:
        if coin > currentChangeCreated + 1: 
            return  currentChangeCreated + 1 
        currentChangeCreated += coin
        
    return currentChangeCreated + 1
```

 

时间复杂度O(nlogn) 排序， 实际nlogn（排序）+n（遍历求和），

空间复杂度O(1)

##### **参考及引用**

https://www.algoexpert.io/questions/Non-Constructible%20Change

使用数学方法表示https://leetcode-cn.com/problems/maximum-number-of-consecutive-values-you-can-make/solution/ni-neng-gou-zao-chu-lian-xu-zhi-de-zui-d-hlxf/

图片from [陳丁光](https://www.facebook.com/groups/474930279315210/user/100010173011046/?__cft__[0]=AZUqqoOu0HSd-Psltvp4WY3-OVt6ZiMwH51QoSF_tE74yC467xLELfdFdVBMqaW7KSneR3nO1dFKaYZlxX1h86i_mwvG5auRJq9IvrjT633gFyFExDf9Nfzir1QuhhlEu_dRicnHp1ZE-OHoE99znoy0kT9C4ApTLr7iT8hpDmV2PFv0zEsogkUdV9ahs4xtGhA&__tn__=-UC*F)