আমাদেরকে একটি অ্যারে দেওয়া হয়েছে [] যার মধ্যে শুধুমাত্র 0 এবং 1 রয়েছে। লক্ষ্য হল arr[] এর সমস্ত সাবঅ্যারে গণনা করা যাতে প্রতিটি সাবঅ্যারেতে শুধুমাত্র 0 থাকে বা শুধুমাত্র 1 উভয়ই থাকে না। যদি অ্যারেটি [1,0,0] হয়। সাবারেগুলি শুধুমাত্র 0 এর জন্য [0], [0], [0,0] এবং 1 এর শুধুমাত্র [1] এর জন্য হবে।
আসুন উদাহরণ দিয়ে বুঝতে পারি।
ইনপুট − arr[] ={ 0, 0, 1, 1, 1, 0 };
আউটপুট − শুধুমাত্র 0 এর সাথে সাবাররে হল :4টি মাত্র 1 এর সাথে সাবাররে হল :6
ব্যাখ্যা − সুবারায় −
হবেFor all 0’s: [0], [0], [0], [0,0]. Total 4 ( arr[0], arr[1], arr[5], arr[0-1] ) For all 1’s: [1], [1], [1], [1,1], [1,1], [1,1,1]. Total 6 ( arr[2], arr[2], arr[4], arr[2-3], arr[3-4], arr[2-4] )
ইনপুট − arr[] ={ 1,0,1,0 };
আউটপুট − শুধুমাত্র 0 এর সাথে সাবাররে হল :2টি মাত্র 1 এর সাথে সাবাররে হল :2
ব্যাখ্যা − সুবারায় −
হবেFor all 0’s: [0], [0]. Total 2 ( arr[1], arr[3] ) For all 1’s: [1], [1]. Total 2 ( arr[0], arr[2] )
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
শুধুমাত্র 0 এবং 1 এর সাথে আলাদাভাবে সাব্যারে গণনার জন্য আমরা অ্যারেটি দুবার অতিক্রম করব। অ্যারেতে পরপর 0 এবং 1 এর গণনা সংরক্ষণ করতে দুটি কাউন্টার count_0 এবং count_1 নিন। এই ধরনের প্রতিটি গণনার জন্য, সম্ভাব্য সাবঅ্যারে হবে count_0*(count_0+1)/2 এবং অনুরূপভাবে count_1 এর জন্য।
অ্যারের শেষ না হওয়া পর্যন্ত এটিকে total_0 গণনায় যোগ করুন। 1 এর জন্য অনুরূপ প্রক্রিয়া করুন।
-
সংখ্যার একটি অ্যারে অ্যারে নিন।
-
ফাংশন sub_zero_one(int arr[], int size) অ্যারে নেয় এবং শুধুমাত্র 0's সহ সাবয়ারের গণনা এবং শুধুমাত্র 1's সহ সাবয়ারের গণনা প্রদান করে৷
-
সাবয়ারের জন্য temp_0 এবং temp_1 হিসাবে প্রাথমিক গণনা নিন।
-
গণনা_0 এবং গণনা_1 হিসাবে 0 এবং 1 এর সাময়িক ধারাবাহিক গণনা নিন।
-
আমরা i=0 থেকে I
-
যদি বর্তমান উপাদান 0 বৃদ্ধি গণনা_0 হয়।
-
যদি তা না হয়, temp_one_0=count*(count+1)/2 হিসাবে 0 এর কাউন্ট_0 সংখ্যা সহ সমস্ত সম্ভাব্য সাব্যারে গণনা করুন।
-
এখন পর্যন্ত পাওয়া সমস্ত 0 সহ সাবয়ারের জন্য এটিকে পূর্ববর্তী temp_0 এ যোগ করুন।
-
1 এর জন্য কাউন্ট_1, temp_one_1 এবং temp_1 হিসাবে ভেরিয়েবল সহ লুপের জন্য অনুরূপ একটি প্রক্রিয়া করুন।
-
উভয় ট্রাভার্সালের শেষে, temp_0 এবং temp_1 এর মধ্যে সমস্ত সাব্যারেগুলির স্বতন্ত্র গণনা থাকবে যেগুলির সমস্ত 0 এবং সমস্ত 1 আছে৷
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void sub_zero_one(int arr[], int size){
int count_1 = 0;
int count_0 = 0;
int temp_1 = 0;
int temp_0 = 0;
for (int i = 0; i < size; i++){
if (arr[i] == 1){
count_1++;
}
else{
int temp_one_1 = (count_1) * (count_1 + 1) / 2;
temp_1 = temp_1 + temp_one_1;
count_1 = 0;
}
}
for (int i = 0; i < size; i++){
if (arr[i] == 0)
{ count_0++; }
else{
int temp_one_0 = (count_0) * (count_0 + 1) / 2;
temp_0 = temp_0 + temp_one_0;
count_0 = 0;
}
}
if (count_1){
int temp_one_1 = (count_1) * (count_1 + 1) / 2;
temp_1 = temp_1 + temp_one_1;
}
if (count_0){
int temp_one_0 = (count_0) * (count_0 + 1) / 2;
temp_0 = temp_0 + temp_one_0;
}
cout<<"Subarrays with only 0's are : "<<temp_0;
cout<<"\nSubarrays with only 1's are : "<<temp_1;
}
int main(){
int arr[] = { 0, 0, 0, 1, 1, 0, 1};
int size = sizeof(arr) / sizeof(arr[0]);
sub_zero_one(arr, size);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেSubarrays with only 0's are : 7 Subarrays with only 1's are : 4
