আমরা ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়. লক্ষ্য হল একটি অ্যারের মধ্যে সংখ্যার সাববারেগুলি খুঁজে বের করা যাতে প্রতিটি সাব্যারেতে সমান সংখ্যক জোড় এবং বিজোড় উপাদান থাকে। যদি অ্যারেটি হয় { 1,2,3,4 }। তাহলে সাবয়ারে হবে {1,2}, {2,3}, {3,4}, {1,2,3,4}। এই ধরনের সাবয়ারের সংখ্যা হল 4।
আসুন উদাহরণ দিয়ে বুঝতে পারি
ইনপুট − arr[] ={1,3,5,7,8,3,2 };
আউটপুট − একই জোড় এবং বিজোড় উপাদান সহ সাবয়ারের সংখ্যা হল − 4
ব্যাখ্যা − সাবাররেগুলি হবে − { 7,8 }, {8,3} {3,2}, {7,8,3,2}
ইনপুট − arr[] ={2,4,6};
আউটপুট − একই জোড় এবং বিজোড় উপাদান সহ সাবয়ারের সংখ্যা হল − 0
ব্যাখ্যা − সমস্ত উপাদান সমান।
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
এই পদ্ধতিতে, আমরা অ্যারের উপাদানগুলির মধ্যে পার্থক্য হিসাবে একটি পরিবর্তনশীল টেম্প ব্যবহার করব (প্রাথমিকভাবে 0) এবং এটিকে 1 দ্বারা বৃদ্ধি করব যদি arr[i] বিজোড় হয় এবং arr[i] জোড় হয় তবে এটি 1 দ্বারা হ্রাস করব। যখন temp-এর মান নিজেই পুনরাবৃত্তি হয় তখন এই সূচকগুলির মধ্যে একই সংখ্যক জোড়-বিজোড় সংখ্যা সহ একটি সাবঅ্যারে থাকতে হবে। তাপমাত্রা ইতিবাচক পাশাপাশি নেতিবাচক হতে পারে। ধনাত্মক পার্থক্যের ফ্রিকোয়েন্সি arr_1[size+1] এবং নেতিবাচক পার্থক্যের ফ্রিকোয়েন্সির জন্য arr_2[size+1] দুটি হ্যাশ অ্যারে নেওয়া।
প্রতিটি পার্থক্য টেম্পের জন্য <0 গণনা করতে arr_1[-temp] থেকে ফ্রিকোয়েন্সি যোগ করুন। [ -(-temp)] একটি ইতিবাচক সূচক দেয়।
প্রতিটি পার্থক্যের জন্য temp> 0 গণনা করতে arr_2[temp] থেকে ফ্রিকোয়েন্সি যোগ করুন। যেহেতু একই পার্থক্য মানের সমস্ত ঘটনাগুলি সাবারেগুলির অংশ হবে। এই ফ্রিকোয়েন্সিগুলি 1 দ্বারা আপডেট করুন।
Arr[] = { 1,3,5,7,8,3,2 } টেম্প মান 0 −
থেকে শুরু হয়1,2,3,4,3,4,3
arr_1[] { 1,1,1,3,2,0,0,0 } //all differences are positive
arr_2[] { 0,0,0,0,0,0,0,0 } //no difference is negative
Adding arr_1[temp] to count in each iteration gives count=4. সাব্যারেগুলি হল − { 7,8 }, {8,3} {3,2}, {7,8,3,2}
-
প্রারম্ভিক অ্যারেটিকে arr[] হিসাবে নিন।
-
ফাংশন Sub_even_odd(int arr[], int size) অ্যারে এবং এর দৈর্ঘ্য নেয় এবং একই জোড় এবং বিজোড় উপাদান সহ সাবয়ারের গণনা প্রদান করে।
-
প্রারম্ভিক গণনাকে 0 হিসাবে এবং পরিবর্তনশীল টেম্পকে একটি পরিবর্তনশীল হিসাবে নিন যা একটি বিজোড় মানের সম্মুখীন হলে বৃদ্ধি পায় এবং একটি জোড় মান সম্মুখীন হলে হ্রাস পায়৷
-
তাপমাত্রার ফ্রিকোয়েন্সি সংরক্ষণ করতে দুটি অ্যারে arr_1[] এবং arr_2[] নিন। arr_1[] টেম্পের ইতিবাচক মানের জন্য যা পুরো অ্যারে সমান হলে সাইজ+1 পর্যন্ত হতে পারে।
arr_2[] টেম্পের নেতিবাচক মানের জন্য যা পুরো অ্যারে সমান হলে সাইজ+1 পর্যন্ত হতে পারে।
-
ট্রাভার্স arr[] লুপ ব্যবহার করে।
-
যদি arr[i] &1==1 মানে arr[i] বিজোড়। তাপমাত্রা বৃদ্ধি। অন্যথায় তাপমাত্রা হ্রাস।
-
যদি temp<0 হয় তাহলে গণনা করতে arr_2[] থেকে সংশ্লিষ্ট ফ্রিকোয়েন্সি যোগ করুন। সেই ফ্রিকোয়েন্সি 1 দ্বারা বৃদ্ধি করুন।
-
যদি temp> 0 হয় তাহলে গণনা করতে arr_1[] থেকে সংশ্লিষ্ট ফ্রিকোয়েন্সি যোগ করুন। সেই ফ্রিকোয়েন্সি 1 দ্বারা বৃদ্ধি করুন।
-
শেষ পর্যন্ত, আমরা arr[] এ সাবয়ারের সংখ্যা হিসাবে গণনা করেছি যেগুলির মধ্যে সমান সংখ্যক জোড় এবং বিজোড় উপাদান রয়েছে
-
ফলাফল হিসাবে রিটার্ন গণনা।
উদাহরণ
#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
