作れない最小の硬貨の合計

作れない最小の硬貨の合計

与えられた硬貨で作れない最初の正の金額を求めてください。

このチャレンジで学べること

与えられた硬貨の中から任意の部分集合を選ぶことができます。同じ値の硬貨が複数枚あっても、それぞれ別の硬貨として1回ずつしか使えません。どの選び方でも作れない最小の正の整数金額を求めてください。

missing_coin_sum(coins) を実装してください。

coins: 利用可能な硬貨の額面のリストです。同じ値が複数回現れる場合、それぞれ別の硬貨を表します。

どの選び方でも作れない最小の正の金額を返してください。

1 ≤ 硬貨の枚数 ≤ 200,000。各硬貨の値は 1 以上 1,000,000,000 以下です。

例 1

入力：
coins = [1, 1, 4]

期待される出力：
expected = 3

入力：
std::vector<long long> coins = {1, 1, 4};

期待される出力：
long long expected = 3;

入力：
long[] coins = new long[] {1, 1, 4};

期待される出力：
long expected = 3;

金額1と2は1円硬貨を使って作れますが、合計3を作れる部分集合はありません。

例 2

入力：
coins = [2, 3]

期待される出力：
expected = 1

入力：
std::vector<long long> coins = {2, 3};

期待される出力：
long long expected = 1;

入力：
long[] coins = new long[] {2, 3};

期待される出力：
long expected = 1;

すべての硬貨が2以上なので、金額1を作る方法がありません。

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

硬貨を昇順に並べ、最小の到達可能な和を小さい方から作っていきます。

ヒント 2

次の硬貨が、まだ作れない最小の値より大きければ、その値はもう作れません。

ヒント 3

重複が役立つのは、今の到達範囲をすき間なく広げられるときだけです。

目安の計算量

O(n log n) time, O(1) extra space, excluding sorting implementation details

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。