【JavaScript】部分配列の合計として表せない最小の正の整数を求めるアルゴリズム

問題の概要

まず、正の整数が昇順にソートされた配列を考えてみましょう。

const arr = [1, 3, 6, 10, 11, 15];

このような配列を引数として受け取り、「元の配列の部分配列（要素の集まり）の合計として表すことができない最小の正の整数」を返す関数 findSmallest() を作成します。

例えば、上記の配列の場合、どの部分配列を足し合わせても到達できない最小の正の整数は「2」です。それでは、この関数のコードを書いていきましょう。

アルゴリズムの考え方

配列があらかじめソートされているため、この問題は線形時間 O(n) で解くことができます。

手順は以下の通りです。

最初に、答えとなる候補値を「1」で初期化します。これは、答えが取り得る最小の値が1だからです。

続いて、配列を先頭から順に走査し、注目している要素を候補値に加算していきます。このとき、もし現在の要素が候補値よりも大きければ、そこで答えが確定します。なぜなら、それまでの要素の合計でカバーできる範囲に欠落が生じていることを意味するからです。要素が候補値以下であるうちは、走査を継続します。

コード例

const arr = [1, 3, 6, 10, 11, 15];
const findSmallest = arr => {
   let res = 1;
   for(let ind = 0; ind < arr.length && arr[ind] <= res; ind++){
      res += arr[ind];
   }
   return res;
};
console.log(findSmallest(arr));

実行結果

コンソールには次のように出力されます。

2