C++で先頭に0、その後に1が来るようにバイナリ配列を分割するための最小トグル回数

問題文

0と1のみを含むn個の整数からなる配列が与えられます。この配列を「前半がすべて0、後半がすべて1」という形に分割するために必要な最小のトグル回数（0を1に、または1を0に切り替える操作）を求めてください。

例

例えば、arr[] = {1, 0, 0, 1, 1, 1, 0} の場合、必要なトグル回数は2回です。具体的には、先頭の「1」と末尾の「0」をそれぞれ切り替えます。

アルゴリズム

• 問題を注意深く観察すると、インデックス0からn-1の間に必ず境界点が存在し、その点より左側にはすべての0が、右側にはすべての1が配置されるべきであることが分かります。
• この規則に当てはまらない要素は切り替え（トグル）の対象となります。そこで、左から右へ向かって0の出現回数を累積的に数えていくという考え方を用います。

各位置iを境界としたとき、必要なトグル回数は次の2つの合計として計算できます。

左側のコスト： 境界より左にある1の個数 ＝ i − zeroCnt[i]
右側のコスト： 境界より右にある0の個数 ＝ zeroCnt[n] − zeroCnt[i]

すべての境界位置についてこの値を評価し、その最小値を答えとします。この手法により、計算量はO(n)となり、単純な総当たり的なO(n²)の解法よりも効率的に処理できます。

実装例

#include <bits/stdc++.h>
using namespace std;
int getMinToggles(int *arr, int n) {
    int zeroCnt[n + 1] = {0};
    for (int i = 1; i <= n; ++i) {
        if (arr[i - 1] == 0) {
            zeroCnt[i] = zeroCnt[i - 1] + 1;
        } else {
            zeroCnt[i] = zeroCnt[i - 1];
        }
    }
    int result = n;
    for (int i = 1; i <= n; ++i) {
        result = min(result, i - zeroCnt[i] + zeroCnt[n] - zeroCnt[i]);
    }
    return result;
}
int main() {
    int arr[] = {1, 0, 0, 1, 1, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum toggles = " << getMinToggles(arr, n) << endl;
    return 0;
}

出力

Minimum toggles = 2

上記のプログラムをコンパイルして実行すると、この結果が出力されます。このコードでは、zeroCnt配列を使って先頭からi番目までに含まれる0の個数を累積的に記録しています。その後、各位置を境界としたときの「左側に残る1の数」と「右側に現れる0の数」の合計（＝必要なトグル回数）を求め、その最小値を返す仕組みです。