আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে শুধু ০ এবং ১ রয়েছে। লক্ষ্য হলো সব সাবঅ্যারে যাতে শুধু ০ থাকে অথবা শুধু ১ থাকে (দুটো একসাথে নয়), তাদের সংখ্যা বের করা। যদি অ্যারে [1,0,0] হয়। ০-র সাবঅ্যারে: [0], [0], [0,0] এবং ১-র সাবঅ্যারে: [1]।
উদাহরণ দিয়ে বুঝি
ইনপুট − arr[] = { 0, 0, 1, 1, 1, 0 };
আউটপুট − শুধু ০-র সাবঅ্যারে: ৪, শুধু ১-র সাবঅ্যারে: ৬
ব্যাখ্যা − সাবঅ্যারে গুলো:
সব ০-র: [0], [0], [0], [0,0]. মোট ৪ (arr[0], arr[1], arr[5], arr[0-1]) সব ১-র: [1], [1], [1], [1,1], [1,1], [1,1,1]. মোট ৬ (arr[2], arr[3], arr[4], arr[2-3], arr[3-4], arr[2-4])
ইনপুট − arr[] = { 1,0,1,0 };
আউটপুট − শুধু ০-র সাবঅ্যারে: ২, শুধু ১-র সাবঅ্যারে: ২
ব্যাখ্যা − সাবঅ্যারে গুলো:
সব ০-র: [0], [0]. মোট ২ (arr[1], arr[3]) সব ১-র: [1], [1]. মোট ২ (arr[0], arr[2])
প্রোগ্রামে ব্যবহৃত পদ্ধতি
আমরা অ্যারে দুবার ট্রাভার্স করব: আলাদা আলাদা ০ এবং ১-র সাবঅ্যারে কাউন্ট করার জন্য। দুটি কাউন্টার count_0 এবং count_1 নিব רציף ০ এবং ১ কাউন্ট করার জন্য। প্রতিটি কাউন্টের জন্য সম্ভাব্য সাবঅ্যারে হবে count_0*(count_0+1)/2 এবং একইভাবে count_1-এর জন্য। এটাকে মোট কাউন্টে যোগ করব।
- অ্যারে
arr[]নিন। sub_zero_one(int arr[], int size)ফাংশন অ্যারে নিয়ে শুধু ০ এবং শুধু ১-র সাবঅ্যারে কাউন্ট রিটার্ন করে।- প্রাথমিক কাউন্ট:
temp_0এবংtemp_1। - রציף কাউন্ট:
count_0এবংcount_1। i=0থেকেi<sizeপর্যন্ত লুপে: যদিarr[i]==1হয়,count_1++। নহলেcount_1দিয়ে সাবঅ্যারে গণনা করুনtemp_one_1 = count_1*(count_1+1)/2,temp_1-এ যোগ করুন,count_1=0রিসেট করুন।- একই প্রক্রিয়া ০-র জন্য দুहरান।
- শেষে যদি
count_1বাcount_0নন-জিরো থাকে, বাকি সাবঅ্যারে যোগ করুন। - ফলাফল প্রিন্ট করুন।
উদাহরণ
#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
