JavaScriptで配列の要素が2乗の関係かどうかをチェックする方法

問題

2つの数値の配列 arr1 と arr2 をそれぞれ第1・第2引数として受け取るJavaScript関数を作成することを考えます。

この関数は、arr2 のすべての要素が、出現順序に関係なく arr1 のいずれかの要素の2乗と一致する場合にのみ true を返し、それ以外の場合は false を返す必要があります。

たとえば、関数への入力が次のようであった場合を考えてみましょう。

入力

const arr1 = [4, 1, 8, 5, 9];
const arr2 = [81, 1, 25, 16, 64];

出力

const output = true;

この場合、81 = 9²、1 = 1²、25 = 5²、16 = 4²、64 = 8² となり、arr2 のすべての要素が arr1 の対応する要素の2乗であるため、結果は true になります。

解決のアプローチ

この問題は、次の手順で効率的に解くことができます。

• まず、両方の配列の長さが一致しているかを確認します。長さが異なれば、すべての要素が対応できないため false を返します。
• 次に、arr1 の各要素を2乗した値の出現回数をマップ（オブジェクト）に記録します。
• 最後に、arr2 の各要素について、その値がマップ内に存在し、かつ残りの使用回数があるかを確認します。存在しなければ false を返します。
• すべての要素が問題なく対応できれば true を返します。

この方法では、重複する要素も正しく処理でき、計算量は O(n) と効率的です。

コード例

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

const arr1 = [4, 1, 8, 5, 9];
const arr2 = [81, 1, 25, 16, 64];

const isSquared = (arr1 = [], arr2 = []) => {
   // 要素数が異なる場合は成立しない
   if (arr1.length !== arr2.length) {
      return false;
   }
   // arr1 の各要素の2乗の出現回数を記録
   const countMap = {};
   for (const num of arr1) {
      countMap[num * num] = (countMap[num * num] || 0) + 1;
   }
   // arr2 の各要素が2乗のマップに含まれるか確認
   for (const num of arr2) {
      if (!countMap[num]) {
         return false;
      }
      countMap[num]--;
   }
   return true;
};

console.log(isSquared(arr1, arr2));

出力

true

コードの解説

このコードのポイントは以下の通りです。

• countMap を使うことで、arr1 内に同じ値が複数存在するケースでも、対応する2乗の個数を正確に管理できます。
• arr2 側の各要素を見つけるたびにカウントを減算するため、「同じ2乗を必要以上に再利用してしまう」誤判定を防げます。
• 配列の長さチェックを最初に行うことで、明らかに成立しないケースを早期に除外できます。

このように、単純な二重ループによる O(n²) の総当たりではなく、ハッシュマップを活用することで線形時間での判定が可能になります。