Day 04 : 找不出的零钱 Non-constructible Change

先来看一下题目

Given an array of positive integers (representing coins), find the smallest value that cannot be constructed from those integers.

这题算是网路蛮多人分享的找零钱变形题，实作起来很简单，其实难度也不高，但是如果没有看过遇过，突然被考到还真的会想不到好的作法！

我们一起来推推看吧！
简单来说这题题目就是在问:
假设给你一堆金币(都是大於０的数) ，找出这些金币不能组出来的最小值
当然我们不可以重复用同样的金币，不然如果给你1块就全部都可以凑出来了!

一开始看到题目很直觉的想法就是:
从1开始确认，1有没有办法被这些数字组成, 2, 3, ... → 暴力
我相信大家一开始都会觉得很简单啊解完了！但这觉对不是最好的方式！

『再想想有没有更好的方式？』
（很常在解题目毫无头绪的时候，看到有Array就可以想到排序）

如果先把array排序会有帮助吗？因为是找是找最小值，应该有帮助吧？

假设 input : [6, 4, 5, 1, 1, 8, 9]
sortedInput -> [1, 1, 4, 5, 6, 8, 9]

我们从1开始，先把一开始可以凑到的最多金额数设为 0 （currentMax = 0）
取出sortedInput[0]= 1 -> 把 currentMax ０加上１-> currentMax = １
也就是我们可以凑到的最多为1

接着我们又可以拿到 sortedInput[1]= 1
所以 １＋１＝２ (currentMax = 2)
我们现在可以凑到的数为 {1, 2}

接着我们拿到 4
4 - 2 = 2 > 1
我们现在最大可以凑到的数是 1 + 1 + 4 = 6
我们现在可以凑到的数为 {1, 2, 4, 5, 6}

那3要怎麽凑呢？ (没错答案就是3)
在这里我们可以发现，每次我们在凑钱的时候，
如果拿到下一个数，和前面加起来目前凑到最大的数相差大於1，那个数就是答案。

欸等等，为什麽？ <- (我一开始看到别人这样做的时候的反应！)

我们来想想！
我们每次在检查当下的数时都存了当下可以组成的最大的数，
而我们知道下一个想要组合而成的数都是当下组成的最大的数+1(也就是目前走到input array地方的所有数和＋１)
那个如果下一个数不是刚好是组成的最大的数+1,
我们不就没有办法拿到其他的数来得到目前组成的最大的数+1吗?
是不是瞬间有头绪了！！

Time Complexity: O(nlogn) -> 时间主要花在排序，只用检查一次阵列
Space Complexity: O(1) (or O(n) 如果不能使用in place sort)

最後来看程序码吧！

function nonConstructibleChange(coins) {
  coins.sort((a,b) => a-b);
	let currentMax = 0;
	for(const coin of coins){
		if (coin > currentMax + 1) return currentMax + 1;
		currentMax += coin;
	}
  return currentMax + 1;
}

Reference: Elements of Programming Interviews in python, page 189

明日题目预告:
入门不可以错过的题目 Two Sum