C++-এ অ্যারেতে p অন্তত q বার এবং q অন্তত p বার থাকা জোড়া সংখ্যা গণনা

আমাদের একটি পজিটিভ ইন্টিজার অ্যারে দেওয়া আছে। লক্ষ্য হল এমন জোড়া (p, q) বের করা যাতে p অ্যারেতে অন্তত q বার থাকে এবং q অ্যারেতে অন্তত p বার থাকে।

উদাহরণ

ইনপুট: arr[] = {3, 3, 3, 5, 5, 6, 6}

আউটপুট: ১

ব্যাখ্যা: শুধু (3,3) ভ্যালিড কারণ ৩ টি بار ৩ আছে।

ইনপুট: arr[] = {3, 3, 3, 3, 3, 5, 5, 5, 6, 6}

আউটপুট: ৩

ব্যাখ্যা: ভ্যালিড জোড়া: (3,3), (5,5), (3,5) — কারণ ৩ পাঁচবার এবং ৫ তিনবার আছে।

অ্যালগরিদম

1. অ্যারে এবং এর আকার ইনপুট নিন।
2. ফ্রিকোয়েন্সি গণনা করার জন্য unordered_map এবং ইউনিক এলিমেন্টের জন্য vector ব্যবহার করুন।
3. প্রতিটি ইউনিক এলিমেন্ট vec[i] এর জন্য:
• যদি ফ্রিকোয়েন্সি vec[i]-এর চেয়ে ছোট হয়, স্কিপ করুন।
• যদি ফ্রিকোয়েন্সি সমান হয়, কাউন্ট বাড়ান।
• যদি ফ্রিকোয়েন্সি বড় হয়, কাউন্ট বাড়ান এবং vec[i]+1 থেকে ফ্রিকোয়েন্সি পর্যন্ত লুপ চালিয়ে যেসব সংখ্যার ফ্রিকোয়েন্সি vec[i]-এর চেয়ে বড় বা সমান, সেগুলোও কাউন্ট করুন।
3. মোট কাউন্ট ফেরত দিন।

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 i = 0; i < vec.size(); i++) {
        if (um[vec[i]] < vec[i]) continue;
        else if (um[vec[i]] == vec[i]) count++;
        else {
            count++;
            for (int j = vec[i] + 1; j <= um[vec[i]]; j++) {
                if (um[j] >= vec[i]) count++;
            }
        }
    }
    return count;
}

int main() {
    int arr[] = {1, 1, 1, 5, 5, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least p times are: " 
         << pair_count(arr, size);
    return 0;
}

আউটপুট

Count of pairs (p, q) such that p occurs in array at least q times and q occurs at least p times are: 1