C++で奇数の合計を持つ部分配列の個数を求める方法

部分配列（サブ配列）とは、配列から連続した形で取り出される一部分のことです。例えば、配列 [5, 6, 7, 8] を考えた場合、(5)、(6)、(7)、(8)、(5, 6)、(6, 7)、(7, 8)、(5, 6, 7)、(6, 7, 8)、(5, 6, 7, 8) のように、10個の空でない部分配列が存在します。

本記事では、C++で「各要素の合計が奇数となる部分配列」の個数を求める方法について詳しく解説します。奇数和を持つ部分配列の個数を求めるには複数のアプローチがありますので、まずは具体的な例から確認していきましょう。

入力 : array = {9,8,7,6,5}
出力 : 9

説明 :
部分配列の合計 -
{9} = 9
{7} = 7
{5} = 5
{9,8} = 17
{8,7} = 15
{7,6} = 13
{6,5} = 11
{8,7,6} = 21
{9,8,7,6,5} = 35

総当たり法（ブルートフォース）

このアプローチでは、すべての部分配列について要素の合計が偶数か奇数かを単純にチェックします。合計が偶数であればその部分配列を対象から除外し、合計が奇数となる部分配列のみをカウントしていきます。実装は非常にシンプルですが、二重ループが必要となるため計算量は O(n²) となり、大規模な配列に対しては非効率です。

コード例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n=5, temp = 0;
    int a[n-1] = { 9,8,7,6,5 } ; // 配列の宣言
    int cnt = 0; // カウンタ変数
    for(int i = 0; i < n; i++){
        temp = 0; // 合計値を初期化
        for(int j = i; j < n; j++){ // 位置iから始まる部分配列を順に作成
            temp = temp + a[j];
            if( temp % 2 == 1 )
                cnt++;
        }
    }
    cout << "Number of subarrays with odd sum : " << cnt << "\n";
    return 0;
}

出力

Number of subarrays with odd sum : 9

コードの解説

このコードではネストされたループを使用しています。外側のループは配列の先頭から各要素を順に指す変数 i を進める役割を担い、内側のループは位置 i から始まる部分配列を一つずつ生成しながら合計を計算し、その合計が奇数になるものを数えています。

効率的なアプローチ

次に紹介するのは、線形時間で動作する効率的な手法です。配列の先頭（0番目の位置）から各要素を順番に処理していきます。現在の要素が偶数であれば偶数カウンタを、奇数であれば奇数カウンタを増やします。ここで重要なポイントは、部分配列に奇数を加えると合計の偶奇（パリティ）が反転するという性質です。そのため、奇数の要素が見つかったタイミングで偶数カウンタと奇数カウンタの値を入れ替えます。そして、各反復処理のたびに奇数カウンタの値を結果に加算していきます。すべての要素を一度だけ処理するため、このコードの計算量は O(n) です。

コード例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int odd = 0, even = 0, result = 0, n=5, i, temp;
    int arr[ n-1 ] = { 9,8,7,6,5}; // 配列の初期化
    // 配列の各要素を処理するforループ
    for ( i = 0 ; i < n ; i ++ ) {
        if ( arr[ i ] % 2 == 0 ) {
            even++;
        } else {
            // 偶数カウンタと奇数カウンタの値を入れ替える
            temp = even;
            even = odd;
            odd = temp + 1;
        }
        result += odd;
    }
    cout << "Number of subarrays with odd sum : " << result;
}

出力

Number of subarrays with odd sum : 9

コードの解説

このコードでは、各要素が偶数か奇数かを判定し、偶数なら偶数カウンタを、奇数なら奇数カウンタをインクリメントします。さらに、奇数の要素が見つかった場合には偶数・奇数カウンタの値を入れ替えます。これは、部分配列に奇数を加えると合計のパリティが反転するためです。そして、各反復処理の後に奇数カウンタの値を結果変数へ加算することで、最終的に奇数和を持つ部分配列の総数が得られます。

まとめ

本記事では、奇数の合計を持つ部分配列の個数を求める2つの方法を解説しました。1つ目は総当たり法で、すべての部分配列を生成し、合計が奇数になるものをカウントしていきます。このコードの時間計算量は O(n²) です。2つ目は効率的なアプローチで、配列の各要素を順に調べながら偶数・奇数カウンタ変数を更新し、奇数が見つかった時点でカウンタを入れ替えるというものです。このコードの時間計算量は O(n) であり、大きな配列を扱う場合に有利です。本記事が、問題の理解と解法の習得の一助となれば幸いです。