C++を使用して奇数の合計を持つサブ配列の数を見つける

サブアレイは、アレイの連続した部分です。たとえば、配列[5、6、7、8]を考えた場合、（5）、（6）、（7）、（8）、（5、6）、（6）のような空でないサブ配列が10個あります。 、7）、（7,8）、（5,6,7）、（6,7,8）および（5,6,7,8）。

このガイドでは、C++で合計が奇数のサブ配列の数を見つけるために考えられるすべての情報について説明します。合計が奇数のサブ配列の数を見つけるために、さまざまなアプローチを使用できるため、ここにその簡単な例を示します-

Input : array = {9,8,7,6,5}
Output : 9

Explanation :
Sum of subarray -
{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 } ; // declaring our array.
    int cnt = 0; // counter variable.
    for(int i = 0; i < n; i++){
        temp = 0; // refreshing our temp sum.
        for(int j = i; j < n; j++){ // this loop will make our subarrays starting from i till n-1.
            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}; // initialising the array
     // for loop for processing every element of array
    for ( i = 0 ; i < n ; i ++ )  {
        if ( arr[ i ] % 2 == 0 ) {
            even++;
        } else {
          // swapping even odd values
            temp = even;
            even = odd;
            odd = temp + 1;
        }
        result += odd;
    }
    cout << "Number of subarrays with odd sum : " << result;
}

出力

Number of subarrays with odd sum : 9

上記のコードの説明

このコードでは、すべての要素の偶数/奇数をチェックし、偶数の場合は偶数カウンターを、奇数の場合は奇数カウンターをインクリメントします。また、奇数が見つかった場合は、奇数と偶数のカウンター値を交換します。それ以外の場合は、サブアレイのパリティが変更されます。次に、反復ごとに奇数カウンターの値を結果変数に追加します。

結論

この記事では、合計が奇数のすべてのサブアレイを生成し、カウントをインクリメントするブルートフォースアプローチから、合計が奇数のサブアレイの数を見つける方法について説明しました。このコードの時間計算量はO（n2）です。効率的なアプローチは、配列の各要素を調べ、奇数/偶数が見つかるたびに奇数/偶数カウンター変数をインクリメントし、奇数が見つかった場合はカウンターを交換することです。このコードの時間計算量はO（n）です。この記事が問題と解決策を理解するのに役立つことを願っています。