আমাদের একটি পজিটিভ ইন্টিজার অ্যারে দেওয়া আছে। লক্ষ্য হলো এমন সাবঅ্যারে খুঁজে বের করা যাতে প্রতিটি সাবঅ্যারেতে জোড় (even) এবং বিজোড় (odd) উপাদানের সংখ্যা সমান। উদাহরণস্বরূপ, অ্যারে {1,2,3,4} হলে সাবঅ্যারে: {1,2}, {2,3}, {3,4}, {1,2,3,4}। মোট ৪টি।
উদাহরণ দিয়ে বুঝি
ইনপুট − arr[] = {1,3,5,7,8,3,2 };
আউটপুট − সমান জোড়-বিজোড় উপাদান বিশিষ্ট সাবঅ্যারে: ৪
ব্যাখ্যা − সাবঅ্যারে: {7,8}, {8,3}, {3,2}, {7,8,3,2}
ইনপুট − arr[] = {2,4,6 };
আউটপুট − সমান জোড়-বিজোড় উপাদান বিশিষ্ট সাবঅ্যারে: ০
ব্যাখ্যা − সব উপাদান জোড়।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
এই পদ্ধতিতে আমরা একটি ভেরিয়েবল temp ব্যবহার করব যা অ্যারে উপাদানগুলোর পার্থক্য ট্র্যাক করবে (শুরুতে ০)। arr[i] বিজোড় হলে temp++, জোড় হলে temp--। যখন temp-এর মান পুনরাবৃত্তি হয়, তখন ওই দুটি ইনডেক্সের মাঝপথে সমান জোড়-বিজোড় উপাদান থাকবে। temp পজিটিভ ও নেগেটিভ উভয় হতে পারে। দুটি হ্যাশ অ্যারে arr_1[size+1] (পজিটিভ পার্থক্যের ফ্রিকোয়েন্সি) এবং arr_2[size+1] (নেগেটিভ পার্থক্যের ফ্রিকোয়েন্সি) ব্যবহার করা হয়।
temp < 0 হলে arr_2[-temp]-এর ফ্রিকোয়েন্সি count-এ যোগ করুন। temp > 0 হলে arr_1[temp]-এর ফ্রিকোয়েন্সি যোগ করুন। ফ্রিকোয়েন্সি ১ বাড়ান।
Arr[] = { 1,3,5,7,8,3,2 }
Temp মান (০ থেকে শুরু): 1,2,3,4,3,4,3
arr_1[] { 1,1,1,3,2,0,0,0 } // সব পার্থক্য পজিটিভ
arr_2[] { 0,0,0,0,0,0,0,0 } // কোনো পার্থক্য নেগেটিভ নেই
প্রতিটি ইটারেশনে arr_1[temp] যোগ করলে count=4।
সাবঅ্যারে: {7,8}, {8,3}, {3,2}, {7,8,3,2}
- প্রাথমিক অ্যারে
arr[]। Sub_even_odd(int arr[], int size)ফাংশন অ্যারে এবং দৈর্ঘ্য নিয়ে সমান জোড়-বিজোড় সাবঅ্যারে কাউন্ট রিটার্ন করে।- প্রাথমিক
count=0,temp=0। - দুটি অ্যারে
arr_1[],arr_2[]ফ্রিকোয়েন্সি স্টোর করতে। সাইজsize+1। arr_1[0] = 1সেট করুন।i=0থেকেsizeপর্যন্ত লুপে:arr[i] & 1 == 1হলে বিজোড়,temp++। অন্যথায়temp--।temp < 0হলেcount += arr_2[-temp],arr_2[-temp]++।temp > 0হলেcount += arr_1[temp],arr_1[temp]++।
countরিটার্ন করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int Sub_even_odd(int arr[], int size) {
int count = 0;
int temp = 0;
int arr_1[size + 1] = {0};
int arr_2[size + 1] = {0};
arr_1[0] = 1;
for (int i = 0; i < size; i++) {
if (arr[i] & 1 == 1) {
temp++;
} else {
temp--;
}
if (temp < 0) {
count += arr_2[-temp];
arr_2[-temp]++;
} else {
count += arr_1[temp];
arr_1[temp]++;
}
}
return count;
}
int main() {
int arr[] = {3, 4, 6, 1, 2, 4, 10, 42};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count of subarrays with same even and odd elements are: " << Sub_even_odd(arr, size);
return 0;
}
আউটপুট
Count of subarrays with same even and odd elements are: 4
