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

ある数値が格納された配列があるとします。この配列の要素の合計を偶数にするために、最小でいくつの数を追加する必要があるかを求めるのが本記事の目的です。ただし、追加する数は0より大きい正の整数でなければなりません。

ルールはシンプルです。要素の合計が奇数の場合は1を追加すれば偶数になります。一方、合計がすでに偶数である場合は、0を追加することが許されていないため、最小の正の偶数である2を追加することになります。

アルゴリズム

addMinNumber(arr)

begin
    s := 0
    for each element e from arr, do
        s := e + s
    done
    if s is even, then return 2, otherwise 1
end

処理の流れ

1. 配列内のすべての要素を順番に足し合わせて、合計値 s を求めます。
2. 合計値 s が偶数であれば 2 を返し、奇数であれば 1 を返します。

サンプルコード（C++）

#include<iostream>
using namespace std;
int addMinNumber(int arr[], int n) {
    int sum = 0;
    for(int i = 0; i<n; i++) {
        sum += arr[i];
    }
    return (sum % 2)? 1 : 2;
}
main() {
    int arr[] = {5, 8, 4, 7, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum " << addMinNumber(arr, n) << " should be added";
}

出力結果

Minimum 1 should be added

コードの解説

この例では、配列 {5, 8, 4, 7, 5} の合計は 5 + 8 + 4 + 7 + 5 = 29 となり、奇数です。そのため、関数 addMinNumber() は 1 を返し、「Minimum 1 should be added（最小で1を追加すべき）」という結果が出力されます。

このアルゴリズムの計算量は O(n) であり、配列を一度走査するだけで答えが求まるため、非常に効率的な手法といえます。