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