C++で配列の合計を偶数にするための最小削除数を求める方法

問題文

N個の整数からなる配列 arr[] が与えられたとします。残りの要素の合計が偶数となるようにするために、配列から取り除くべき要素の最小個数を求めるプログラムを作成します。

例

入力配列が {10, 20, 30, 5} の場合、配列全体の合計は65（奇数）です。この合計を偶数にするには、要素「5」を1つ取り除くだけで十分で、その結果 合計は60（偶数）になります。したがって、答えは「1」となります。

アルゴリズム

この問題は、偶数と奇数の加法における基本的な性質を利用することで、非常にシンプルに解くことができます。

1. 偶数をいくつ足し合わせても、合計は常に偶数になります。
2. 奇数を奇数個足し合わせると、合計は常に奇数になります。
3. 奇数を偶数個足し合わせると、合計は常に偶数になります。
4. そこで、配列内の奇数の個数をカウントします。奇数の個数が偶数であれば、どの要素も取り除く必要はありません。逆に、奇数の個数が奇数であれば、奇数の要素を任意に1つ取り除くだけで合計を偶数にできます。

つまり、答えは常に「0」または「1」のいずれかになります。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;

int getMinRemovals(int *arr, int n) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] % 2 == 1) {
            ++cnt;
        }
    }
    return (cnt % 2 == 0) ? 0 : 1;
}

int main() {
    int arr[] = {10, 20, 30, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum required removals = " << getMinRemovals(arr, n) << endl;
    return 0;
}

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

出力

Minimum required removals = 1

計算量について

このアルゴリズムは配列を一度走査するだけなので、時間計算量は O(n)、追加のメモリ使用量は O(1) となり、非常に効率的です。