C++で合計が偶数のサブ配列の数を検索します

この問題では、N個の要素で構成される配列arr[]が与えられます。私たちのタスクは、合計が偶数のサブ配列を見つけることです。

問題を理解するために例を見てみましょう

入力

arr[] = {2, 1, 3, 4, 2, 5}

出力

28

説明

サブアレイは-

{2}, {4}, {2}, {2, 4}, {2, 2}, {1, 3}, {1, 5}, {3, 5}, {4, 2}, {2, 1, 3}, {2, 1, 5}, {2, 3, 5}, {2, 4, 2}, {1, 3, 4}, {1, 3, 2}, {1, 4, 5}, {1, 2, 5}, {3, 4, 5}, {3, 2, 5}, {2, 1, 3, 4}, {2, 1, 3, 2}, {2, 3, 4, 5}, {2, 3, 2, 5}, {2, 4, 2, 5}, {1, 3, 4, 2}, {1, 4, 2, 5}, {3, 4, 2, 5}, {2, 1, 3, 4, 2}, {2, 1, 3, 4, 2, 5}

ソリューションアプローチ

この問題の簡単な解決策は、すべてのサブアレイとその合計を計算する直接法を使用することです。そして、合計が偶数のサブアレイの増加カウント。そして最後にリターンカウント。

ソリューションの動作を説明するプログラム

例

#include<iostream>
using namespace std;
int countEvenSumSubArray(int arr[], int n){
   int evenSumCount = 0, sum = 0;
   for (int i=0; i<=n-1; i++){
      sum = 0;
      for (int j=i; j<=n-1; j++){
         sum += arr[j];
      if (sum % 2 == 0)
         evenSumCount++;
      }
   }
   return (evenSumCount);
}
int main(){
   int arr[] = {2, 1, 4, 2};
   int n = sizeof (arr) / sizeof (arr[0]);
   cout<<"The count of Subarrays with even sum is "<<countEvenSumSubArray(arr, n);
   return (0);
}

出力

The number of solutions of the linear equation is 8