JavaScriptで配列を「2倍関係」を満たすように再配置できるか判定する方法

問題

数値の配列 arr を第一引数（唯一の引数）として受け取るJavaScript関数を作成する必要があります。

配列 arr の長さは必ず偶数であると保証されています。

この関数は、すべての 0 <= i < arr.length / 2 に対して arr[2 * i + 1] = 2 * arr[2 * i] という条件を満たすように並べ替えられる場合にのみ true を返し、そうでなければ false を返す必要があります。

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

const arr = [4, -2, 2, -4];

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

const output = true;

出力の説明

配列を [-2, -4] と [2, 4] の2つのペアに分割できます。どちらのペアも「隣り合う要素の後ろが前の要素のちょうど2倍」という関係を満たしているため、これらを連結した [-2, -4, 2, 4] や [2, 4, -2, -4] といった並べ替え結果が条件を満たします。よって答えは true となります。

解決アプローチ

この問題は、ハッシュマップ（オブジェクト）で各数値の出現回数を記録し、値の大小順にペアを消費していくことで効率的に解決できます。ポイントは次のとおりです。

• キーを数値として昇順にソートしてから処理します。
• 負の数は、絶対値が大きい側（ソート順で先頭側）から処理し、その半分の値（ゼロに近い側）とのペアを探します。
• 正の数および0は、小さい側から処理し、その2倍の値とのペアを探します。
• 必要なペアがマップ上に存在しない場合は、並べ替えが不可能と判断して即座に false を返します。

計算量はソートに伴う O(n log n) となり、大規模な配列でも実用的な速度で動作します。

コード例

const arr = [4, -2, 2, -4];

const canRearrange = (arr = []) => {
    // 各数値の出現回数をカウント
    const map = arr.reduce((acc, num) => {
        acc[num] = (acc[num] || 0) + 1;
        return acc;
    }, {});

    // キーを数値として昇順ソート
    const keys = Object.keys(map)
        .map(key => Number(key))
        .sort((a, b) => a - b);

    for (const key of keys) {
        if (key < 0) {
            // 負の数：半分の値とのペアを確認
            while (map[key] > 0) {
                if (map[key / 2] > 0) {
                    map[key] -= 1;
                    map[key / 2] -= 1;
                } else {
                    return false;
                }
            }
        } else {
            // 正の数・0：2倍の値とのペアを確認
            while (map[key] > 0) {
                if (map[key * 2] > 0) {
                    map[key] -= 1;
                    map[key * 2] -= 1;
                } else {
                    return false;
                }
            }
        }
    }
    return true;
};

console.log(canRearrange(arr));

実行結果

このコードをコンソールで実行すると、次のような出力が得られます。

true

入力配列 [4, -2, 2, -4] は条件を満たす並べ替えが可能であるため、関数は true を返しています。もし余分な要素やペアにならない要素が存在すれば、途中で false が返されます。