Non-Constructible Change

目录隐藏

问题：

给定一系列正整数，代表硬币的面值，找到无法从这些整数组连续组合成的最小值。比如 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 陳丁光

Non-Constructible Change

问题：

解答：

参考及引用

garlic