JavaScriptでソートされていない配列から欠落している1つの数字を見つける方法

問題の概要

1からnまでの連続した整数が含まれるはずの配列を受け取り、欠落している1つの数字を見つけて返すJavaScript関数を作成します。この配列には次の2つの特徴があります。

• 1つの数字だけが欠落している
• 要素がランダムな順序で格納されている（未ソート）

解決のアプローチ：等差数列の和の公式

最もシンプルかつ効率的な方法は、ガウスの和の公式を利用することです。1からnまでの整数の合計は「n × (n + 1) ÷ 2」で求めることができます。

具体的な手順は以下の通りです。

1. 実際の合計：reduce()メソッドを使って、配列内の全要素の合計を計算する
2. 理論上の合計：欠落した数字を含む完全な数列の合計を公式から算出する
3. 差分を求める：理論値から実際の合計を引くと、それがまさに欠落している数字になる

この方法なら、配列をソートする必要がなく、計算量はO(n)で済むため非常に高速です。

コード例

以下が実際のコードです。

const arr = [4, 7, 1, 8, 9, 5, 2, 3];
const findMissing = (arr = []) => {
    // 配列内の全要素の合計を計算
    const sumArr = arr.reduce((acc, val) => acc + val);
    const { length: len } = arr;
    // 完全な数列（1〜len+1）の理論上の合計を計算
    const sumFirst = (len + 1) * (len + 2) * .5;
    // 差分が欠落している数字
    const missing = sumFirst - sumArr;
    return missing;
};
console.log(findMissing(arr));

コードのポイント

ここで注目すべき点は、配列の長さがlenの場合、本来含まれるべき数字は1からlen + 1までであるという点です。そのため、理論上の合計を計算する際は(len + 1)と(len + 2)を使用しています。

また、* .5による掛け算は「÷2」と同じ意味で、浮動小数点演算を避けたい場合は/ 2としても同じ結果になります。

出力結果

6

サンプルの配列[4, 7, 1, 8, 9, 5, 2, 3]には8個の要素があり、本来は1〜9の数字が含まれるはずです。この中で欠けているのが6であり、プログラムも正しく6を出力しています。

まとめ

ソート不要・線形時間で動作するこの手法は、面接や競技プログラミングでも頻出の定番テクニックです。配列の順序に依存せず、合計値の差分だけで欠損値を特定できる点が大きな魅力と言えるでしょう。