सरणी में ऐसे जोड़े (p, q) जिनमें p कम से कम q बार आता है और q कम से कम p बार आता है - C++

समस्या विवरण

हमें धनात्मक पूर्णांकों का एक ऐरे दिया गया है। लक्ष्य उन जोड़ों (p, q) की गणना करना है जहाँ:

• p सरणी में कम से कम q बार आता है
• q सरणी में कम से कम p बार आता है

उदाहरण

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

आउटपुट: 1

व्याख्या: केवल (3,3) वैध है क्योंकि 3 ठीक 3 बार आता है।

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

आउटपुट: 3

व्याख्या: वैध जोड़े: (3,3), (5,5), (3,5) — क्योंकि 3 पाँच बार आता है और 5 तीन बार आता है।

दृष्टिकोण

प्रत्येक अद्वितीय तत्व की आवृत्ति गिनें। फिर प्रत्येक अद्वितीय मान v के लिए:

• यदि freq[v] < v → छोड़ दें
• यदि freq[v] == v → गणना बढ़ाएँ
• यदि freq[v] > v → गणना बढ़ाएँ और j = v+1 से freq[v] तक जाँचें कि क्या freq[j] >= v

एल्गोरिदम

1. आवृत्ति मैप um और अद्वितीय मानों का वेक्टर vec बनाएँ
2. प्रारंभिक count = 0
3. vec में प्रत्येक मान v के लिए:
   • यदि um[v] < v जारी रखें
   • अन्यथा यदि um[v] == v तो count++
   • अन्यथा:
     • count++
     • j = v+1 से um[v] तक लूप करें
     • यदि um[j] >= v तो count++
4. count लौटाएँ

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

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

int pair_count(int arr[], int len) {
    int count = 0;
    vector<int> vec;
    unordered_map<int, int> um;
    
    for (int i = 0; i < len; i++) {
        um[arr[i]]++;
        if (um[arr[i]] == 1) vec.push_back(arr[i]);
    }
    
    for (int v : vec) {
        if (um[v] < v) continue;
        else if (um[v] == v) count++;
        else {
            count++;
            for (int j = v + 1; j <= um[v]; j++) {
                if (um[j] >= v) count++;
            }
        }
    }
    return count;
}

int main() {
    int arr[] = {1, 1, 1, 5, 5, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << pair_count(arr, size);
    return 0;
}

आउटपुट

Count: 1