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

問題文

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

例

入力配列が {10, 20, 30, 5, 7} の場合について考えてみます。この配列の合計は 72 という偶数であるため、合計を奇数にするには要素を1つ削除する必要があります。具体的には、「5」または「7」のいずれかを取り除けば条件を満たせます。

アルゴリズム

この問題は、偶数と奇数の足し算に関する以下の基本的な性質を利用すると効率的に解くことができます。

1. 偶数をいくつ足し合わせても、その合計は必ず偶数になる
2. 奇数を奇数個足し合わせた場合、合計は必ず奇数になる
3. 奇数を偶数個足し合わせた場合、合計は必ず偶数になる
4. 以上より、配列内の奇数の要素数をカウントする。カウントが偶数であれば合計も偶数になるため要素を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) ? 1 : 0;
}

int main() {
    int arr[] = {10, 20, 30, 5, 7};
    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) となります。

注意点

配列に奇数の要素が1つも含まれていない場合（すべての要素が偶数の場合）、どの要素を削除しても合計は偶数のままとなり、合計を奇数にすること自体が不可能です。上記のサンプルコードではこのケースが考慮されていないため、実務で利用する際には奇数要素が存在するかどうかのチェックを追加しておくとより安全です。