JavaScriptで配列からn番目の欠落数を見つける方法

問題の概要

1ずつ増加する数列があり、その一部の要素が欠落している状況を考えてみましょう。

const arr = [2,3,4,7,11];

このような配列を第1引数として、整数nを第2引数として受け取り、配列の中でn番目に欠けている数値を見つけるJavaScript関数を作成する必要があります。

具体例

上記の配列に対して n = 4 が与えられた場合、期待される出力は 8 です。

なぜなら、この配列に含まれていない数値（欠落数）は次の通りだからです。

1, 5, 6, 8

4番目の欠落数が 8 であるため、関数は 8 を返すことになります。

解決策：コード例

const arr = [2, 3, 4, 7, 11];
const findMissing = (arr = [], n) => {
    let el = 0;
    let diff = 0;
    for(let i=0; i<arr.length; ++i) {
        const difference = arr[i] - el - 1;
        const sum = diff + difference;
        if(sum>=n) {
            break;
        };
        diff = sum;
        el = arr[i];
    }
    return el + n - diff;
};
console.log(findMissing(arr, 4));

コードの仕組み

変数 el は直前に確認した配列の要素を、diff はそれまでに発見された欠落数の累計を表します。ループ内では隣接する要素同士の差分から各区間の欠落数を計算し、その累計が n 以上になった時点で処理を中断します。最後に el + n - diff を返すことで、目的となるn番目の欠落数を効率的に算出しています。

出力結果

このコードを実行すると、コンソールには以下の出力が表示されます。

8