আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে শুধু ০ এবং ১ রয়েছে। লক্ষ্য হলো এমন সাবঅ্যারে গুলোর সংখ্যা বের করা যাতে ০ এবং ১-এর ঘটনা (occurrence) সমান। উদাহরণস্বরূপ, অ্যারে [1,0,0] হলে সাবঅ্যারে: [1,0] মাত্র।
উদাহরণ দিয়ে বুঝি
ইনপুট − arr[] = { 0, 0, 1, 1, 1, 0 };
আউটপুট − সমান সংখ্যক ০ ও ১ বিশিষ্ট সাবঅ্যারে: ৪
ব্যাখ্যা − সাবঅ্যারে গুলো:
arr[0 to 3] = [0,0,1,1], arr[1 to 2] = [0,1], arr[4 to 5] = [1,0], arr[0 to 5] = [0,0,1,1,1,0]
ইনপুট − arr[] = { 0, 1, 1, 1, 1 };
আউটপুট − সমান সংখ্যক ০ ও ১ বিশিষ্ট সাবঅ্যারে: ১
ব্যাখ্যা − সাবঅ্যারে: arr[0 to 1] = [0,1]
প্রোগ্রামে ব্যবহৃত পদ্ধতি
দুটি for লুপ দিয়ে সব সম্ভাব্য সাবঅ্যারে জেনারেট করব। i=0 থেকে size-1 এবং j=i থেকে size-1। সাবঅ্যারে arr[i] থেকে arr[j]। প্রতিটি সাবঅ্যারেতে ০ এবং ১-এর ফ্রিকোয়েন্সি কাউন্ট করব। সমান হলে কাউন্ট বাড়াব।
- অ্যারে
arr[]নিন। sub_zeroes_ones(int arr[], int size)ফাংশন অ্যারে নিয়ে সমান ০-১ সাবঅ্যারে কাউন্ট রিটার্ন করে।- প্রাথমিক কাউন্ট ০।
- দুটি লুপ:
i=0থেকেsize-1,j=iথেকেsize-1। total_0,total_1০ ইনিশিয়ালাইজ করুন।arr[j]০ হলেtotal_0++, ১ হলেtotal_1++।- যদি
total_0 == total_1হয়,count++। - দুই লুপ শেষে
countরিটার্ন করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int sub_zeroes_ones(int arr[], int size) {
int count = 0;
for (int i = 0; i <= size - 1; i++) {
int total_0 = 0;
int total_1 = 0;
for (int j = i; j <= size - 1; j++) {
if (arr[j] == 0) {
total_0++;
} else if (arr[j] == 1) {
total_1++;
}
if (total_0 == total_1) {
count++;
}
}
}
return count;
}
int main() {
int arr[] = {0, 1, 1, 0, 0};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count of subarrays with equal number of 1's and 0's are: " << sub_zeroes_ones(arr, size);
return 0;
}
আউটপুট
Count of subarrays with equal number of 1's and 0's are: 4
