এই সমস্যায়, আমাদের 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
দক্ষ পদ্ধতি (হ্যান্ডশেক সূত্র)
একটি আরও দক্ষ পদ্ধতি হল হ্যান্ডশেক সূত্র ব্যবহার করা। আমরা একটি টেম্প অ্যারে তৈরি করব ০ এবং ১-এর অকুরেন্স গণনা করার জন্য মডুলো অ্যারেতে। এবং তারপর কাউন্ট ভ্যালু রিটার্ন করব।
প্রোগ্রাম উদাহরণ (দক্ষ পদ্ধতি)
#include <iostream>
using namespace std;
int countEvenSumSubArray(int arr[], int n){
int temp[2] = {1, 0};
int count = 0, sum = 0;
for (int i = 0; i <= n-1; i++){
sum = ((sum + arr[i]) % 2 + 2) % 2;
temp[sum]++;
}
count += (temp[0] * (temp[0] - 1) / 2);
count += (temp[1] * (temp[1] - 1) / 2);
return count;
}
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 count of Subarrays with even sum is 4
