JavaScriptで等差数列から欠落している数字を効率的に見つける方法

等差数列（Arithmetic Progression）とは

等差数列（AP）とは、隣り合う項どうしの差が常に一定であるような数列のことを指します。

たとえば「5, 7, 9, 11, 13…」という数列は、各項の差が2で一定であるため、典型的な等差数列です。

問題設定

ここで、等差数列の要素が順番に並んだ配列があるとします。しかし、何らかの理由でその数列から1つの数字だけが欠落してしまったとしましょう。

求められているのは、この配列を第1引数（唯一の引数）として受け取るJavaScript関数です。この関数は、1回の走査（イテレーション）だけで欠落している数字を見つけ出し、それを返す必要があります。

たとえば、入力配列が次の場合を考えてみましょう。

const arr = [7, 13, 19, 31, 37, 43];

このとき、期待される出力は次のとおりです。

const output = 25;

これは、25が19と31の間に存在するべき数字であり、まさに欠落している値だからです。実際、公差は6であり、19 + 6 = 25、25 + 6 = 31となり、数列が成立します。

解決のアプローチ

この問題を効率的に解くポイントは以下のとおりです。

• まず配列の先頭2要素の差（diff1）と末尾2要素の差（diff2）を比較します。
• 両者が一致しない場合、欠落しているのは先頭付近か末尾付近です。diff1がdiff2のちょうど2倍であれば、先頭側に欠落があります。そうでなければ末尾側に欠落があります。
• 両者が一致する場合は、その差が正しい公差なので、途中の要素を順番に調べていき、公差と異なる箇所を見つけたら、そこに欠落があると判断できます。

この方法により、最悪でも配列を1回通過するだけで答えが得られるため、計算量はO(n)に抑えられます。

実装例

以上の考え方を実装すると、コードは次のようになります。

const arr = [7, 13, 19, 31, 37, 43];
const findMissingNumber = (arr = []) => {
    let {length} = arr;
    let diff1 = arr[1] - arr[0];
    let diff2 = arr[length - 1] - arr[length - 2];
    if (diff1 !== diff2) {
        if (diff1 == 2 * diff2){
            return arr[0] + diff2;
        }else{
            return arr[length - 1] - diff1;
        };
    };
    for (let i = 1; i < length - 2; i++){
        if (arr[i + 1] - arr[i] != diff1){
            return arr[i] + diff1;
        };
    };
    return arr[0];
};
console.log(findMissingNumber(arr));

コードのポイント

関数内では、まず配列の長さを取得し、先頭と末尾それぞれの隣接要素間の差を計算しています。これにより、欠落数字が配列の端に近いケースも、ループに入る前に素早く判定できるのが特徴です。途中のループでは、隣接要素の差が公差と一致しない最初の場所を見つけると、直前の要素に公差を足した値を即座に返します。

出力結果

このコードをコンソールで実行すると、出力は次のようになります。

25

このように、等差数列の性質を利用すれば、欠落した数字をわずかな比較処理だけで特定でき、非常に効率的なアルゴリズムとなります。