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