Tìm số mảng con có tổng chẵn trong C ++

Trong bài toán này, chúng ta được đưa ra một mảng arr [] gồm N phần tử. Nhiệm vụ của chúng ta là tìm mảng con có tổng chẵn.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

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

Đầu ra

28

Giải thích

Các mảng con là -

{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}

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là sử dụng phương pháp trực tiếp bằng cách tính toán tất cả các mảng con và tổng của chúng. Và số lượng tăng lên cho mảng con có tổng chẵn. Và ở số lần trả lại cuối cùng.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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);
}

Đầu ra

The number of solutions of the linear equation is 8