JavaScriptで数値の配列に対してべき乗演算を実行する方法

問題

私たちは、偶数の長さを持つ整数の配列 arr を引数として受け取る JavaScript 関数を記述する必要があります。

ここで、次のような数値 num を考えます −

num = (arr[0] * arr[0] + arr[1] * arr[1]) * (arr[2] * arr[2] + arr[3] * arr[3]) * … * (arr[n-2] * arr[n-2] + arr[n-1] * arr[n-1])

このとき n は配列の長さを表します。つまり、配列を隣り合う2つの要素ごとのペアに分割し、各ペアの平方和をすべて掛け合わせた値が num となります。

この関数は、次の条件を満たす2つの数値からなる配列 [A, B] を見つけて返す必要があります −

A2 + B2 = num

例えば、入力配列が次の場合 −

[1, 2, 3, 4]

まず num を計算すると、num = (1 + 4) × (9 + 16) = 125 となります。

したがって、期待される出力は −

[2, 11]

これは、2² + 11² = 4 + 121 = 125 が成立するためです。

解法のアプローチ

この問題は、次の2段階の処理で解くことができます。

ステップ1: num の計算
配列を先頭から2つずつのペアに分け、各ペアについて (a² + b²) を計算し、それらを順に掛け合わせます。この構造は複素数の積に関連しています。ブラーマグプタ＝フィボナッチ恒等式によれば、(a² + b²)(c² + d²) は必ず2つの整数の平方和の形で表せるため、答えが存在することが保証されます。

ステップ2: 平方和への分解
求めた num に対して、k² + j² = num を満たす非負の整数 k と j を二重ループによる総当たりで探索します。条件が一致した時点で [k, j] を返します。

例

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

const arr = [1, 2, 3, 4];
const findMatchingSumArray = (arr = []) => {
    let squaredSum = 1;
    for(let i = 0; i < arr.length - 1; i += 2){
        const curr = arr[i];
        const next = arr[i + 1];
        squaredSum *= (Math.pow(curr, 2) + Math.pow(next, 2));
    };
    for(let k = 0; k * k < squaredSum; k++){
        for(let j = 0; (k * k) + (j * j) <= squaredSum; j++){
            if((k * k) + (j * j) === squaredSum){
                return [k, j];
            };
        };
    };
    return [];
};
console.log(findMatchingSumArray(arr));

出力

コンソールには次の出力が表示されます −

[2, 11]