[演算法題目] Non-Constructible Change

本題資訊

難度：easy
使用語言：C++
相關概念：Arrays

題目敘述

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.

Input:
coins = [5, 7, 1, 1, 2, 3, 22]

Output:
20

Idea

題目還蠻簡單的，有一點像小時候湊硬幣的感覺。

因為是要找出最小的不能湊出的數字，所以首先想到的就是從最小的開始累加，並想辦法找出斷層。這個斷層也很好找，下個數字若是比目前累加的數字的下一個還要大，那就表示有斷層。

紅色是 coins 累加結果，底線是 coins 的元素。這邊可以看到可累加至 19，之後就跳到 22（大於 19+1），無法湊出 20 和 21。

#include <vector>
#include <algorithm>
using namespace std;

int nonConstructibleChange(vector<int> coins) {
  sort(coins.begin(), coins.end());
  int current = 0;

  for (auto x:coins){
    if (x > current + 1){
      return current + 1;
    }
    current += x;
  }
  return current + 1;
}