আমাদেরকে পূর্ণসংখ্যা উপাদান সম্বলিত একটি অ্যারে দেওয়া হয়েছে। লক্ষ্য হল অ্যারের উপাদানগুলির অনন্য জোড়া খুঁজে বের করা যাতে জোড়ার প্রকারের (arr[i], arr[j]) সূচী থাকে যেমন i
আসুন উদাহরণ দিয়ে বুঝতে পারি
ইনপুট − arr[] ={1,2,3};
আউটপুট − অনন্য জোড়ার গণনা (arr[i], arr[j]) যেমন i
ব্যাখ্যা - যেহেতু সমস্ত উপাদান অনন্য। জোড়া হবে −
ইনপুট − arr[] ={ 4,4,3,2};
আউটপুট − অনন্য জোড়ার গণনা (arr[i], arr[j]) যেমন i
ব্যাখ্যা - যেহেতু সমস্ত উপাদান অনন্য। জোড়া হবে −
আমরা দুটি পন্থা ব্যবহার করব। লুপের জন্য একটি ব্যবহার করে প্রথম নিরীহ পদ্ধতি। দুটির জন্য লুপ ব্যবহার করে অ্যারে অ্যারে[] ট্র্যাভার্স করা শুরু করুন। i=0 থেকে i<দৈর্ঘ্য-1 এবং j=i+1 থেকে j<দৈর্ঘ্য। এই ভাবে সবসময় i
পূর্ণসংখ্যার উপাদান এবং আকার হিসাবে দৈর্ঘ্য সহ পূর্ণসংখ্যার অ্যারে [] নিন
ফাংশন unique_pair(int arr[], int size) অ্যারে এবং এর দৈর্ঘ্য নেয় এবং অনন্য জোড়ার সংখ্যা প্রদান করে যেমন জোড়ায় (arr[i],arr[j]) সূচক i
গণনার প্রাথমিক মান 0 হিসাবে নিন।
পূর্ণসংখ্যা জোড়া সম্বলিত একটি সেট 'se' নিন। (সেট
লুপগুলির জন্য দুটি ব্যবহার করে arr[] অতিক্রম করা শুরু করুন। i=0 থেকে i
প্রতিটি জোড়ার জন্য সর্বদা i
লুপের জন্য উভয়ের শেষে, count=se.size().
কাউন্টের এখন 'সে'-তে বেশ কয়েকটি জোড়া রয়েছে। ( সবগুলোই অনন্য)।
ফলাফল হিসাবে রিটার্ন গণনা।
এই পদ্ধতিতে, আমরা প্রতিটি উপাদানের পরে অনন্য উপাদান খুঁজে পাব। arr[i] arr[ i+1 থেকে সাইজ-1 ] থেকে স্বতন্ত্র/অনন্য উপাদানের সাথে যুক্ত হবে। সুতরাং arr[i] এর পরে যদি x অনন্য উপাদান থাকে, তাহলে arr[i] x জোড়া তৈরি করবে। সুতরাং আমরা প্রথমে একটি সূচক i এর পরে অনন্য উপাদান চিহ্নিত করে একটি অ্যারে তৈরি করব। তারপর মোট অনন্য জোড়ার জন্য পৃথক পৃথক সংখ্যা যোগ করুন।
পূর্ণসংখ্যার উপাদান এবং আকার হিসাবে দৈর্ঘ্য সহ পূর্ণসংখ্যার অ্যারে [] নিন
ফাংশন unique_pair(int arr[], int size) অ্যারে এবং এর দৈর্ঘ্য নেয় এবং অনন্য জোড়ার সংখ্যা প্রদান করে যেমন জোড়ায় (arr[i],arr[j]) সূচক i
গণনার প্রাথমিক মান 0 হিসাবে নিন।
টেম্প ভ্যারিয়েবল নিন এবং এটি 0 এ সেট করুন।
দৈর্ঘ্যের আকারের একটি অ্যারে arr_2[] নিন এবং শুরু করুন arr_2[size-1]=0, কারণ শেষ উপাদানটির পরে 0 অনন্য উপাদান রয়েছে।
দুটি পূর্ণসংখ্যা সেট তৈরি করুন চেক এবং আনচেক করুন।
শেষ উপাদান থেকে first.i=size-1 থেকে i>=0 পর্যন্ত ট্রাভার্স অ্যারে। সেট চেকের মধ্যে arr[i] অনুসন্ধান করুন।
যদি না পাওয়া যায় তাহলে অনন্য। তাপমাত্রা বৃদ্ধি (তাপ হল arr[i] এর পরে অনন্য উপাদানের গণনা)। arr_2[i]=temp.
অন্যথায় arr_2[i]=temp. তাপমাত্রা বৃদ্ধি ছাড়াই।
চেক সেট করতে arr[i] ঢোকান। এখন arr[i] এর পরবর্তী ঘটনা বিবেচনা করা হবে না।
এই জন্য লুপ শেষ করার পরে. arr_2[] আপডেট করা হয়েছে।
এখন সূচী i=0 থেকে i
আনচেক সেট করতে arr[i] যোগ করুন। এখন arr[i] এর পরবর্তী ঘটনা বিবেচনা করা হবে না।
শেষে গণনায় অনন্য জোড়া থাকে যেমন i
ফলাফল হিসাবে রিটার্ন গণনা।
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −(1,2) - ( arr[0],arr[1] ) 0<1
(1,3) - ( arr[0], arr[2] ) 0<2
(2,3) - ( arr[1],arr[2] ) 1<2
(4,4) - ( arr[0],arr[1] ) 0<1
(4,3) - ( arr[0], arr[2] ) 0<2
(4,2) - ( arr[0],arr[3] ) 0<3
(3,2) - ( arr[2],arr[3] ) 2<3
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
দক্ষ পদ্ধতি
উদাহরণ (নিষ্পাপ পদ্ধতি)
#include<bits/stdc++.h>
using namespace std;
int unique_pair(int arr[], int size){
int count = 0;
set<pair<int, int>> se;
for(int i = 0; i < (size - 1); i++){
for (int j = i + 1; j < size; j++){
se.insert(make_pair(arr[i], arr[j]));
}
}
count = se.size();
return count;
}
int main(){
int arr[] = { 4, 3, 1, 6, 7 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of unique pairs (arr[i], arr[j]) such that i < j are: "<<unique_pair(arr, size);
return 0;
} আউটপুট
Count of unique pairs (arr[i], arr[j]) such that i & j are: 10
উদাহরণ (দক্ষ পদ্ধতি)
#include<bits/stdc++.h>
using namespace std;
int unique_pair(int arr[], int size){
int count = 0, temp = 0;
int arr_2[size];
arr_2[size-1] = 0;
set<int> check, uncheck;
for (int i = size - 1; i > 0; i--){
auto set = check.find(arr[i]);
if (set != check.end()){
arr_2[i - 1] = temp;
}
else{
arr_2[i - 1] = ++temp;
}
check.insert(arr[i]);
}
for (int i = 0; i < size - 1; i++){
auto set = uncheck.find(arr[i]);
if (set != uncheck.end()){
continue;
}
count += arr_2[i];
uncheck.insert(arr[i]);
}
return count;
}
int main(){
int arr[] = { 4, 3, 1, 6, 7 };
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of unique pairs (arr[i], arr[j]) such that i < j are: "<<unique_pair(arr, size);
return 0;
} আউটপুট
Count of unique pairs (arr[i], arr[j]) such that i < j are: 10
