C++で配列の全要素を4の倍数にするための最小操作回数を求める

問題文

サイズ n の整数配列が与えられたとき、配列内のすべての要素を4で割り切れるようにするために必要な最小の操作回数を求めます。ここで1回の操作とは、「配列から任意の2つの要素を取り除き、その合計値を新しい要素として配列に追加する」ことを指します。

例

入力配列が {1, 2, 0, 2, 4, 3} の場合、必要な操作は2回です。

1 + 3 = 4
2 + 2 = 4

0 と 4 はもともと4で割り切れるため、これらを組み合わせる操作は不要です。したがって、正解は2となります。

アルゴリズム

1. 配列の全要素の合計が4で割り切れない場合、どのように操作しても条件を満たせないため、不可能と判定します（-1を返します）。
2. サイズ4の配列 modulus をすべて0で初期化します。
3. 操作回数を記録するカウンタ count を0で初期化します。
4. 入力配列を走査し、各要素を4で割った余りを求めます。
5. 余りに対応する modulus の要素を1増やします。
6. modulus[0] はすでに4で割り切れる要素の個数なので、他の要素と組み合わせる必要はありません。
7. modulus[1]（余り1）と modulus[3]（余り3）の要素同士を組み合わせると4の倍数になるため、両者のうち小さい方の値だけ count に加算します。
8. modulus[2]（余り2）の要素は、2つ組み合わせることで4の倍数になります。
9. ペアにできずに残った modulus[1]・modulus[3] の要素については、それぞれの半分の値を modulus[2] に加算します（余り1同士、余り3同士を組み合わせると余り2の新しい要素が生まれるためです）。同時に、その半分の値を count にも加算します。
10. 最後に、count に modulus[2] の半分を加算します。2つの要素が1つにまとめられるため、半分の値を使用します。
11. 最終的な count の値が、配列の全要素を4で割り切れるようにするために必要な最小の操作回数となります。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
int getMinRequiredSteps(int arr[], int n) {
    int count = 0;
    int modulus[4] = {0};
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int mod = arr[i] % 4;
        sum += mod;
        modulus[mod]++;
    }
    if (sum % 4 != 0) {
        return -1;
    } else {
        if (modulus[1] > modulus[3]) {
            count += modulus[3];
        }
        else {
            count += modulus[1];
        }
        modulus[1] -= count;
        modulus[3] -= count;
        modulus[2] += modulus[1] / 2;
        modulus[2] += modulus[3] / 2;
        count += modulus[1] / 2;
        count += modulus[3] / 2;
        count += modulus[2] / 2;
        return count;
    }
}
int main() {
    int arr[] = {1, 2, 0, 2, 4, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum required steps = " << getMinRequiredSteps(arr, n) << endl;
    return 0;
}

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

出力

Minimum required steps = 2

計算量

時間計算量: O(n) ― 配列を一度走査するだけで処理が完了します。
空間計算量: O(1) ― サイズ4の補助配列のみを使用するため、入力サイズに依存しないメモリで動作します。