【C++】左右の偶数・奇数の個数が等しくなる配列インデックスを見つけるプログラム

問題の概要

「両側で偶数（または奇数）の個数が同じになる配列インデックス」とは、ある要素の左側と右側に含まれる偶数の個数、または奇数の個数が互いに等しくなるような位置のことです。つまり、「左側の個数＝右側の個数」を満たすインデックスを見つける問題です。

まず、この概念に関連する基本用語を確認しておきましょう。

基本用語の定義

配列（Array）：同じデータ型の要素を格納するためのコンテナ（データ構造）です。

配列インデックス（Array Index）：配列内の要素の位置を示す番号です。インデックスは必ず0から始まります。

偶数：2で割り切れる整数のことです。

奇数：2で割り切れない整数のことです。

すべての整数は、偶数か奇数のいずれかに必ず分類されます。

それでは、具体例を使って概念をより明確にしてみましょう。

入力: arr[] = {4, 3, 2, 1, 2}
出力: 2

解説

この例では、インデックス2（値は「2」）に注目します。左側には奇数「3」が1個あり、右側にも奇数「1」が1個あります。左右の奇数の個数が一致しているため、答えはインデックス2となります。

つまりこの問題は、n個の整数からなる配列が与えられたとき、次のいずれかの条件を満たすインデックスを見つけることを意味します。

• ある要素の左側にある偶数の個数と、右側にある偶数の個数が等しい
• ある要素の左側にある奇数の個数と、右側にある奇数の個数が等しい

条件を満たすインデックスが存在すればその値を出力し、存在しない場合は-1を出力します。

アルゴリズム

両側の偶数・奇数の個数が等しくなる要素のインデックスを求めるには、注目している要素の左側と右側それぞれに含まれる偶数・奇数の個数を数える必要があります。

配列arr[]とその要素数nが与えられた場合の手順は以下の通りです。

Step 1 : iが0からnまで、Step 2〜5を繰り返す
Step 2 : e_l（左側の偶数）、o_l（左側の奇数）、e_r（右側の偶数）、o_r（右側の奇数）を0で初期化する
Step 3 : jが0からi-1まで、e_lとo_lをカウントする
Step 4 : kがi+1からn-1まで、e_rとo_rをカウントする
Step 5 : (e_l == e_r) または (o_l == o_r) の場合、iを出力する

C++による実装例

#include <iostream>
using namespace std;
int main() {
    int arr[] = {4, 3, 2, 1, 2};
    int n = 5;
    cout<<"The array is : ";
    for(int i = 0; i < n; i++) {
        cout<<arr[i]<<" ";
    }
    cout<<"\nThe index of the element with the same count of even or odd numbers on both sides = ";
    for (int i = 0; i < n; i++) {
        int o_l = 0, e_l = 0;
        int o_r = 0, e_r = 0;
        for (int j = 0; j < i; j++) {
            if (arr[j] % 2 == 0)
                e_l++;
            else
                o_l++;
        }
        for (int k = n - 1; k > i; k--) {
            if (arr[k] % 2 == 0)
                e_r++;
            else
                o_r++;
        }
        if (e_r == e_l || o_r == o_l)
            cout<<i<<endl;
    }
    return 0;
}

実行結果

The array is : 4 3 2 1 2
The index of the element with the same count of even or odd numbers on both sides = 2

計算量と改善のポイント

上記の実装では、各インデックスについて左側と右側の要素をそれぞれ走査するため、時間計算量はO(n²)となります。配列全体の偶数・奇数の合計個数を事前に求めておき、要素を左から順に処理しながら累積カウントを更新していく方式にすれば、O(n)まで計算量を削減できます。大きな配列を扱う場合は、この最適化を検討するとよいでしょう。