আমাদের একটি পজিটিভ ইন্টিজার অ্যারে দেওয়া আছে। লক্ষ্য হল এমন জোড়া বের করা যাতে LCM(arr[i], arr[j]) > min(arr[i], arr[j])। নোট: জোড়া (i,j) এবং (j,i) একই, দুবার কাউন্ট করা হবে না।
উদাহরণ
ইনপুট: arr[] = [1,5,4,2]
আউটপুট: ৬
ব্যাখ্যা: সব ৬টি জোড়া শর্ত পূরণ করে।
ইনপুট: arr[] = [3,3,6]
আউটপুট: ২
ব্যাখ্যা: জোড়া: (3,6) দুবার (কারণ দুটি ৩ আছে)।
গ্লimps
শর্তটি মিথ্যা হয় শুধু যখন arr[i] == arr[j]। অর্থাৎ একই মানয়ের জোড়া বাদ দিয়ে বাকি সব জোড়া ভ্যালিড।
অ্যালগরিদম
- ফ্রিকোয়েন্সি ম্যাপ
umতৈরি করুন। - প্রতিটি ফ্রিকোয়েন্সি
fজন্য সমান এলিমেন্টের জোড়া =f*(f-1)/2। এইগুলো বাদ দিন। - মোট জোড়া =
n*(n-1)/2। - উত্তর = মোট জোড়া - সমান এলিমেন্টের জোড়া।
C++ বাস্তবায়ন
#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 f = it.second;
count += f * (f - 1) / 2;
}
int total = size * (size - 1) / 2;
return total - 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
