【JavaScript】配列に要素を追加して0〜numまでの全ての合計を作れる最小追加数を求める

問題概要

数値の配列 arr を第1引数、単一の数値 sum を第2引数として受け取る JavaScript 関数を作成します。

配列に新しい要素を追加していき、[0, sum](両端を含む)の範囲の任意の合計値を、配列内のいくつかの要素を選んで足し合わせることで表現できるようにします。そして最終的に、この条件を満たすために配列へ追加が必要となる要素の最小個数を返します。

入力例

const arr = [1, 5, 10];
const sum = 20;

出力例

const output = 2;

出力の解説

配列に 2 と 4 の2つの数を追加すると、配列は [1, 2, 4, 5, 10] となり、これらの組み合わせによって [0, 20] の範囲のどの合計値でも作り出せるようになります。

たとえば「3」は 1+2、「7」は 2+5、「20」は 10+5+4+1 といった具合に、途中の数値に抜け漏れなく対応できます。

解法コード

この問題は以下のコードで解けます。

const arr = [1, 5, 10];
const sum = 20;

const minimumAddition = (arr = [], sum = 1) => {
    let canAdd = 1;
    let count = 0, i = 0;
    while(canAdd <= sum){
        if((i >= arr.length) || (canAdd < arr[i])){
            count++;
            canAdd += canAdd;
        }else{
            canAdd += arr[i++];
        };
    };
    return count;
};
console.log(minimumAddition(arr, sum));

実行結果

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

2

アルゴリズムのポイント(貪欲法)

この解法の鍵となるのは、変数 canAdd の扱いです。canAdd は「現時点の配列ではまだ作れない最小の合計値」を意味し、初期値は 1 です。

• 配列の次の要素が canAdd 以下の場合:その要素を取り込むことで、作れる合計の範囲は [0, canAdd + arr[i]] まで連続的に拡張されます。
• 配列の次の要素が canAdd より大きい場合、または配列を使い切った場合:ここに穴が開いてしまうため、canAdd 自身を新しい要素として追加する必要があります。追加後、作れる合計の上限は 2 × canAdd へと倍増します。

この処理を canAdd が sum を超えるまで繰り返し、追加した回数 count を返せば答えが得られます。各ステップで配列の要素を1つ消費するか canAdd が倍増するため、計算量はおよそ O(n + log sum) と非常に効率的です。