আমরা ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়. লক্ষ্য হল arr[]-এর উপাদানগুলির জোড়ার গণনা খুঁজে বের করা, যেমন LCM( arr[i], arr[j] )> সর্বনিম্ন ( arr[i], arr[j] )। অর্থাৎ, একটি জোড়ার উপাদানগুলির সর্বনিম্ন সাধারণ গুণফল উভয়ের ন্যূনতম থেকে বেশি৷
দ্রষ্টব্য − জোড়া ( arr[i], arr[j] ) একই ( arr[j], arr[i])। এটাকে দুবার গণনা করবেন না।
আসুন উদাহরণ দিয়ে বোঝা যাক।
ইনপুট − arr[] =[ 1,5,4,2 ]
আউটপুট − একটি অ্যারেতে জোড়ার সংখ্যা যেমন LCM(arr[i], arr[j])> min(arr[i],arr[j]) হল −6
ব্যাখ্যা − মোট 6 জোড়া হল −
Pair 1 (1,5) LCM is 5 > 1 Pair 2 (1,4) LCM is 4 > 1 Pair 3 (1,2) LCM is 2 > 1 Pair 4 (5,4) LCM is 20 > 4 Pair 5 (5,2) LCM is 10 > 2 Pair 6 (4,2) LCM is 4 > 2
ইনপুট − arr[] =[ 3,3,6 ]
আউটপুট − একটি অ্যারেতে জোড়ার সংখ্যা যেমন LCM(arr[i], arr[j])> min(arr[i],arr[j]) হল − 2
ব্যাখ্যা − মোট 2 জোড়া হল −
Pair 1 (3,6) LCM is 6 > 3 Pair 2 (3,6) LCM is 6 > 3
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
উপরের শর্তটি মিথ্যা হবে শুধুমাত্র যেখানে arr[i]==arr[j]। অনন্য উপাদানগুলির মধ্যে জোড়া তৈরি করা হবে। বিন্যাসের অনন্য উপাদানগুলির ফ্রিকোয়েন্সি সহ একটি ক্রমবিহীন মানচিত্র নিন। এখন সমস্ত অনুরূপ উপাদান জোড়া মুছে ফেলার জন্য. প্রতিটি ফ্রিকোয়েন্সির জন্য সর্বাধিক জোড়া হিসাবে গণনা করুন ( freq * (freq-1)/2)। গণনার জন্য এই ধরনের সমস্ত গণনা যোগ করুন।
মোট অ্যারেতে আকারের উপাদান রয়েছে তারপর সর্বাধিক জোড়া=সাইজ(আকার-1)/2।
ফলাফল জোড়া-গণনা হবে. (সমস্ত জোড়া - একই উপাদান সহ জোড়া)।
পূর্ণসংখ্যার একটি অ্যারে নিন।
-
পূর্ণসংখ্যার একটি অ্যারে নিন।
-
ফাংশন conditional_pair(int arr[], int size) অ্যারে এবং এর আকার নেয় এবং জোড়ার সংখ্যা প্রদান করে যাতে শর্ত পূরণ হয়।
-
0 হিসাবে প্রাথমিক গণনা নিন।
-
arr[] এর উপাদান এবং তাদের ফ্রিকোয়েন্সির জন্য unordered_map
-
প্রতিটি ফ্রিকোয়েন্সি temp =it.second এর জন্য এবং জন্য ব্যবহার করে ট্র্যাভার্স ম্যাপ; (it=পুনরাবৃত্ত) গণনা করতে temp*(temp-1)/2 যোগ করুন। উপাদানের তাপমাত্রা সংখ্যার জন্য সমস্ত সম্ভাব্য জোড়া।
-
এখন গণনায় একই উপাদানের সমস্ত জোড়া রয়েছে যা আমাদের ক্ষেত্রে বিবেচনা করা হবে না৷
-
temp=size*(size-1)/2 হিসাবে অ্যারের উপাদানগুলির জন্য মোট সম্ভাব্য জোড়া গণনা করুন।
-
গণনা হিসাবে গণনা আপডেট করুন - তাপমাত্রা।
-
ফলাফল হিসাবে রিটার্ন গণনা।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int conditional_pair(int arr[], int size){
int count = 0;
unordered_map<int, int> um;
for (int i = 0; i < size; i++){
um[arr[i]]++;
}
for (auto it : um){
int temp = it.second;
count = count + temp * (temp - 1) / 2;
}
int temp = (size * (size - 1)) / 2;
count = temp - count;
return count;
}
int main(){
int arr[] = { 4, 1, 7, 3, 2};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs in an array such that LCM(arr[i], arr[j]) > min(arr[i],arr[j]) are:
"<<conditional_pair(arr, size);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount of pairs in an array such that LCM(arr[i], arr[j]) > min(arr[i],arr[j]) are: 10
