আমাদেরকে পূর্ণসংখ্যার উপাদান সম্বলিত একটি অ্যারে arr[] দেওয়া হয়েছে। লক্ষ্য হল জোড়ার সংখ্যা খুঁজে বের করা যা arr[] এর সাব-অ্যারেগুলির উপাদানগুলির দ্বারা গঠিত হতে পারে যেমন প্রতিটি সাবঅ্যারেতে শুধুমাত্র স্বতন্ত্র উপাদান রয়েছে। যদি অ্যারেটি [ 1,2,2,3,3 ] হয় তাহলে শুধুমাত্র স্বতন্ত্র উপাদান সহ সাবয়ারে হবে [ 1,2 ] এবং [ 2,3 ]। এবং জোড়া হবে (1,2) এবং (2,3) তাই জোড়ার সংখ্যা 2।
আসুন উদাহরণ দিয়ে বুঝতে পারি
ইনপুট − arr[] ={1,2,5,3 }
আউটপুট − স্বতন্ত্র উপাদান সাব-অ্যারে দ্বারা গঠিত জোড়ার সংখ্যা হল − 6
ব্যাখ্যা − স্বতন্ত্র উপাদান সহ সাবঅ্যারে হল:[ 1,2,5, 3], সম্ভাব্য জোড়া (1,2), (1,3), (1,5), (2,5), (2,3), (5,3)
মোট ৬ জোড়া।
ইনপুট − arr[] ={1,2,1,2,3}
আউটপুট − স্বতন্ত্র উপাদান সাব-অ্যারে দ্বারা গঠিত জোড়ার সংখ্যা হল −5
ব্যাখ্যা − স্বতন্ত্র উপাদান সহ সাবঅ্যারে হল −
[1,2] - pairs: (1,2) [2,1] - pairs: (2,1) [1,2,3] - pairs : (1,2), (2,3), (1,3) Total pairs : 5
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
-
ইনপুট হিসাবে একটি পূর্ণসংখ্যা অ্যারে নিন।
-
ফাংশন distinct_pairs(int arr[], int size) অ্যারে নেয় এবং স্বতন্ত্র উপাদান সাব-অ্যারে দ্বারা গঠিত কাউন্ট জোড়া ফেরত দেয়।
-
প্রারম্ভিক গণনাটিকে 0 হিসাবে নিন। ভেরিয়েবলগুলি start=end=0।
নিন -
উইন্ডোতে উপাদান চিহ্নিত করতে একটি ভেক্টর চেক (আকার, মিথ্যা) নিন।
-
স্টার্ট লুপ WHILE যতক্ষণ না স্টার্ট সাইজের থেকে কম হয়
-
লুপের ভিতরে, সাইজ থেকে কম শুরু না হওয়া পর্যন্ত আরেকটি লুপ শুরু করুন এবং চেক[arr[স্টার]] =0 তারপর কাউন্ট স্টার্ট - এন্ড হিসাবে সেট করুন এবং চেক[arr[start]] কে সত্য হিসাবে সেট করুন এবং শুরুটিকে 1 দ্বারা বৃদ্ধি করুন।
-
স্টার্ট লুপ যখন শেষ পর্যন্ত স্টার্ট এবং স্টার্ট সাইজের সমান নয় এবং চেক[arr[start]] =true তারপর সেট চেক[arr[end]] =false এবং শেষটি 1 দ্বারা বৃদ্ধি করুন।
-
গণনা ফেরত দিন
-
ফলাফল প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int distinct_pairs(int arr[], int size){
int count = 0;
int start = 0;
int end = 0;
vector<bool> check(size, false);
while (start < size){
while (start < size && !check[arr[start]]){
count += (start - end);
check[arr[start]] = true;
start++;
}
while (end < start && (start != size && check[arr[start]])){
check[arr[end]] = false;
end++;
}
}
return count;
}
int main(){
int arr[] = {5, 1, 8, 2, 1, 7, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs formed by distinct element sub-arrays are: "<< distinct_pairs(arr, size);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of pairs formed by distinct element sub-arrays are: 17
