JavaScriptで配列内の数値とそのn倍の関係を検出する方法

問題の概要

整数の配列を第一引数として、数値 n を第二引数として受け取るJavaScript関数を作成する必要があります。

この関数は、配列内に「一方が他方のn倍」という関係を満たす2つの数値が存在するかどうかを判定します。そのようなペアが存在すれば true を返し、存在しなければ false を返します。

入力例

配列と数値が以下の場合：

const arr = [4, 2, 7, 8, 3, 9, 5];
const n = 4;

出力例

このときの出力は次のようになります。

const output = true;

その理由は、配列内に 2 と 8 という数値が存在し、以下の関係が成り立つからです。

8 = 2 * 4

実装コード

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

const arr = [4, 2, 7, 8, 3, 9, 5];
const n = 4;
const containsNthMultiple = (arr = [], n = 1) => {
    const hash = new Set();
    for(let i = 0; i < arr.length; i++){
        const el = arr[i];
        const [left, right] = [el / n, el * n];
        if(hash.has(left) || hash.has(right)){
            return true;
        };
    hash.add(el);
    };
    return false;
};
console.log(containsNthMultiple(arr, n));

出力結果

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

true

コードの解説

このアルゴリズムのポイントは、Set（ハッシュセット）を使ってこれまで走査した要素を記録している点です。各要素について、「その要素を n で割った値（left）」と「その要素に n を掛けた値（right）」のどちらかがすでに Set 内に存在するかを確認します。存在していれば、n倍の関係を満たすペアが見つかったことになり、即座に true を返します。

この手法により、全要素同士を比較する二重ループ（計算量 O(n²)）を使わずに、線形時間 O(n) で効率的に判定できるのが大きなメリットです。大規模な配列を扱う場合でも高速に動作します。