C++で左右の偶数・奇数の出現回数が一致する配列インデックスを見つける方法

問題の概要

ここで取り上げるのは次のような問題です。n個の要素を持つ配列が与えられたとき、「あるインデックスの左側にある偶数の出現回数と右側にある偶数の出現回数が等しい」、または「左側にある奇数の出現回数と右側にある奇数の出現回数が等しい」という条件を満たすインデックスを1つ見つけます。該当するインデックスが存在しない場合は -1 を返します。

例として、配列が {4, 3, 2, 1, 2, 4} の場合を考えてみましょう。このとき答えは 2 になります。インデックス2の要素は「2」であり、その左側には奇数が1つ（3）、右側にも奇数が1つ（1）しか存在しないためです。

解決のアプローチ

この問題を効率よく解くには、左右それぞれの情報を保持するために、pair（整数のペア）を要素とするvectorを2つ用意します。

• left_vector：各位置より左側に存在する奇数・偶数の出現回数を記録します。
• right_vector：各位置より右側に存在する奇数・偶数の出現回数を記録します。

すべてのインデックスについて、左側と右側で偶数のカウントが一致しているか、奇数のカウントが一致しているかを確認し、条件を満たすインデックスが見つかった時点でその値を返します。

アルゴリズム

getIndex(arr, n) −

Begin
    define odd and even, and initialize as 0
    define left_vector, right_vector for odd even pairs
    add (odd, even) into left_vector
    for i in range 0 to n-2, do
        if arr[i] is even, then increase even, otherwise increase odd
            add (odd, even) into left_vector
    done
    odd := 0 and even := 0
    add (odd, even) into right_vector
    for i in range n-1 down to 1, do
        if arr[i] is even, then increase even, otherwise increase odd
            add (odd, even) into right_vector
    done
    reverse the right_vector
    for each element at index i in left_vector, do
        if left_vector[i].first = right_vector[i].first,
           or left_vector[i].second = right_vector[i].second, then return i
    done
    return -1
End

C++による実装例

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int getIndex(int n, int arr[]) {
    int odd = 0, even = 0;
    vector<pair<int, int >> left_vector, right_vector;
    left_vector.push_back(make_pair(odd, even));
    for (int i = 0; i < n - 1; i++) { //count and store odd and even frequency for left side
        if (arr[i] % 2 == 0)
            even++;
        else
            odd++;
        left_vector.push_back(make_pair(odd, even));
    }
    odd = 0, even = 0;
    right_vector.push_back(make_pair(odd, even)); //count and store odd and even frequency for right side
    for (int i = n - 1; i > 0; i--) {
        if (arr[i] % 2 == 0)
            even++;
        else
            odd++;
        right_vector.push_back(make_pair(odd, even));
    }
    reverse(right_vector.begin(), right_vector.end());
    for (int i = 0; i < left_vector.size(); i++) {
        if (left_vector[i].first == right_vector[i].first ||
            left_vector[i].second == right_vector[i].second)
        return i;
    }
    return -1;
}
int main() {
    int arr[] = {4, 3, 2, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = getIndex(n, arr);
    if(index == -1) {
        cout << "-1";
    } else {
        cout << "index : " << index;
    }
}

このコードでは、まず配列を左から順に走査し、各位置における奇数・偶数の累積出現回数を left_vector に記録していきます。続いて右側から走査して right_vector を作成し、reverse() によってインデックスの対応関係を揃えます。最後に2つのvectorを先頭から比較し、偶数または奇数のカウントが一致する最初のインデックスを返します。どこにも条件を満たす位置がなければ -1 を返します。

計算量は、配列を前後からそれぞれ1回ずつ走査するだけであるため O(n)、必要な補助記憶領域も O(n) です。

実行結果

index : 2

サンプル配列 {4, 3, 2, 1, 2} の場合、インデックス2（要素「2」）の左側には奇数が1つ（3）、右側にも奇数が1つ（1）存在するため、条件を満たすインデックスとして 2 が出力されます。