सरणी में LCM(arr[i],arr[j]) > min(arr[i],arr[j]) वाले जोड़ों की गणना - C++

समस्या विवरण

हमें धनात्मक पूर्णांकों की एक सरणी दी गई है। लक्ष्य उन जोड़ों की गणना करना है जहाँ LCM(arr[i], arr[j]) > min(arr[i], arr[j])। नोट: जोड़ा (i,j) और (j,i) समान है, दो बार न गिनें।

उदाहरण

इनपुट: arr[] = [1,5,4,2]

आउटपुट: 6

व्याख्या: सभी 6 जोड़े शर्त पूरी करते हैं।

इनपुट: arr[] = [3,3,6]

आउटपुट: 2

व्याख्या: (3,6) दो बार (दो अलग-अलग 3 के साथ)। (3,3) का LCM=3 है जो min=3 से बड़ा नहीं है।

मुख्य अंतर्दृष्टि

शर्त केवल तब गलत होती है जब arr[i] == arr[j] हो। सभी विशिष्ट तत्व जोड़े शर्त पूरी करते हैं।

दृष्टिकोण

आवृत्ति मैप बनाएँ। प्रत्येक आवृत्ति f के लिए, समान-तत्व जोड़े = f*(f-1)/2। कुल जोड़े = n*(n-1)/2। उत्तर = कुल - समान_तत्व_जोड़े।

एल्गोरिदम

1. आवृत्ति मैप um बनाएँ
2. same_pairs = 0
3. प्रत्येक आवृत्ति f के लिए: same_pairs += f*(f-1)/2
4. total_pairs = n*(n-1)/2
5. return total_pairs - same_pairs

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

int conditional_pair(int arr[], int size) {
    unordered_map um;
    for (int i = 0; i < size; i++) um[arr[i]]++;
    
    int same_pairs = 0;
    for (auto& it : um) {
        int f = it.second;
        same_pairs += f * (f - 1) / 2;
    }
    
    int total_pairs = size * (size - 1) / 2;
    return total_pairs - same_pairs;
}

int main() {
    int arr[] = {4, 1, 7, 3, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << conditional_pair(arr, size);
    return 0;
}

आउटपुट

Count: 10