আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে পূর্ণসংখ্যা রয়েছে। লক্ষ্য হলো এমন সাবঅ্যারে গুলোর সংখ্যা বের করা যাতে প্রতিটি সাবঅ্যারেতে পৃথক (distinct) উপাদানের সংখ্যা মূল অ্যারেটে পৃথক উপাদানের সংখ্যার সমান। উদাহরণস্বরূপ, মূল অ্যারে [1,1,2,3] হলে পৃথক উপাদান ৩টি (1,2,3)। সাবঅ্যারে: [1,2,3] এবং [1,1,2,3]।
উদাহরণ দিয়ে বুঝি
ইনপুট − arr[] = {1,2,1,2,3,4,2 };
আউটপুট − মূল অ্যারের মতো পৃথক উপাদান সংখ্যা সম্পন্ন সাবঅ্যারে: ৬
ব্যাখ্যা − arr[]-এ পৃথক উপাদান ৪টি (1,2,3,4)। একই পৃথক উপাদান সংখ্যা সম্পন্ন সাবঅ্যারে গুলো (বাম থেকে ডানে পৃথক গণনা):
[1,2,1,2,3,4], [2,1,2,3,4], [1,2,3,4], [1,2,3,4,2], [2,1,2,3,4,2], [1,2,1,2,3,4,2]
ইনপুট − arr[] = {8,7,5,6,10 };
আউটপুট − মূল অ্যারের মতো পৃথক উপাদান সংখ্যা সম্পন্ন সাবঅ্যারে: ১
ব্যাখ্যা − arr[]-এ পৃথক উপাদান ৫টি (5,6,7,8,10)। একই পৃথক উপাদান সংখ্যা সম্পন্ন সাবঅ্যারে: [8,7,6,5,10]। শুধু ১টি।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- অ্যারে
arr[]এবং এর সাইজ নিন। sub_distinct(int arr[], int size)ফাংশন অ্যারে নিয়ে পৃথক উপাদান সমান সাবঅ্যারে কাউন্ট রিটার্ন করে।- অস্থায়ী ভেরিয়েবল
count,right,leftনিন। unordered_mapদিয়ে র্যান্ডম পেয়ার তৈরি করুন।i=0থেকেsizeপর্যন্ত লুপেum[arr[i]] = 1সেট করুন।um.size()বের করেum.clear()করুন।i=0থেকেsizeপর্যন্ত লুপে:while (right < size && left < um_size):++um[arr[right]]- যদি
um[arr[right]] == 1হয়,++left ++right
- যদি
left == um_sizeহয়,count = count + (size - right + 1) --um[arr[i]]- যদি
um[arr[i]] == 0হয়,--left
countরিটার্ন করুন।- ফলাফল প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int sub_distinct(int arr[], int size) {
int count = 0, right = 0, left = 0;
unordered_map<int, int> um;
for (int i = 0; i < size; ++i) {
um[arr[i]] = 1;
}
int um_size = um.size();
um.clear();
for (int i = 0; i < size; ++i) {
while (right < size && left < um_size) {
++um[arr[right]];
if (um[arr[right]] == 1) {
++left;
}
++right;
}
if (left == um_size) {
count = count + (size - right + 1);
}
--um[arr[i]];
if (um[arr[i]] == 0) {
--left;
}
}
return count;
}
int main() {
int arr[] = {4, 3, 2, 5};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count of subarrays having total distinct elements same as original array are: " << sub_distinct(arr, size);
return 0;
}
আউটপুট
Count of subarrays having total distinct elements same as original array are: 1
