C++プログラミング:配列の合計を偶数にするための最小の数を求める方法

問題の概要

与えられた配列に対して、0より大きい最小の数を1つ追加し、配列全体の合計を偶数にする方法を解説します。

入出力例

入力: 1 2 3 4

出力: 2

説明: 配列の合計は10で偶数です。偶数の合計を維持するには、最小でも2を追加する必要があります(1を追加すると合計が奇数になってしまうため)。

方法1:配列の合計を計算して判定する

配列の全要素の合計を計算します。合計が偶数であれば追加する最小の数は2、奇数であれば1となります。

入出力例

入力: 1 2 3 4

出力: 2

説明: 配列の合計は10なので、合計を偶数に保つために最小の数2を追加します。

サンプルコード

#include<iostream>
using namespace std;
int main() {
    int arr[] = { 1, 2, 3, 4};
    int n = 4;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    if (sum % 2 == 0) {
        cout << "2";
    } else {
        cout << "1";
    }
    return 0;
}

方法2:奇数の個数を数える

配列内の奇数の要素をカウントします。奇数の個数が偶数であれば2を返し、奇数であれば1を返します。これは、合計の偶奇が奇数の個数の偶奇によって決まるためです。

入出力例

入力: 1 2 3 4 5

出力: 1

説明: 配列内の奇数は3個あるため、合計を偶数にするために最小の数1を追加します。

サンプルコード

#include<iostream>
using namespace std;
int main() {
    int arr[] = { 1, 2, 3, 4, 5};
    int n = 5;
    int odd = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 != 0) {
            odd += 1;
        }
    }
    if (odd % 2 == 0) {
        cout << "2";
    } else {
        cout << "1";
    }
    return 0;
}

方法3:フラグ変数とNOT演算を活用する

初期値0のフラグ変数を用意し、配列内に奇数の要素を見つけるたびにNOT演算(!)でフラグの値を反転させます。この論理演算子は、フラグが0なら1に、1なら0に切り替えます。

処理の流れ

入力: 1 2 3 4 5 / 出力: 1

• 変数は0で初期化
• 1は奇数 → 変数が1に反転
• 2は偶数 → 変化なし
• 3は奇数 → 変数が0に反転
• 4は偶数 → 変化なし
• 5は奇数 → 変数が1に反転

最終的に変数が1であれば、配列内の奇数の要素が奇数個存在することを意味します。この場合、合計を偶数にするための最小の数は1です。そうでなければ、最小の数は2です。

サンプルコード

#include<iostream>
using namespace std;
int main() {
    int arr[] = { 1, 2, 3, 4, 5};
    int n = 5;
    bool odd = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 != 0) {
            odd = !odd;
        }
    }
    if (odd) {
        cout << "1";
    } else {
        cout << "2";
    }
    return 0;
}

まとめ

いずれの方法でも計算量はO(n)となり、配列を1回走査するだけで答えを求められます。特に方法3はカウンタ変数が不要で、フラグ変数1つで判定できるため、メモリ使用量の観点でも効率的な実装といえます。