---
# System prepended metadata

title: '-Non-Constructible change'
tags: [Easy]

---

# -Non-Constructible change
###### tags: `Easy`
![](https://i.imgur.com/0rzWPpB.png)

求零錢堆中之最小不可得數目: 
用了sort -> O(nlogn) time
想法: 從最小的數開始累積，如果遇到大於目前已累積數目的零錢，即遇到斷層-> 停止，如果沒就繼續加
![](https://i.imgur.com/CLashHW.png)

```cpp=
#include <vector>
using namespace std;

int nonConstructibleChange(vector<int> coins) {
  // Write your code here.
  int cur_change = 0;
  sort(coins.begin(), coins.end());
  for (auto x:coins){
      if (x > cur_change + 1) 
          return cur_change + 1;
      cur_change += x;
  }
  return cur_change + 1;
}
```
