C++-এ অ্যারেতে গড়ও উপস্থিত থাকা জোড়া সংখ্যা গণনা

আমাদের একটি ইন্টিজার অ্যারে দেওয়া আছে (এলিমেন্ট রেঞ্জ: [-1000, 1000])। লক্ষ্য হল এমন জোড়া বের করা যাদের গড় (average)ও অ্যারেতে উপস্থিত।

উদাহরণ

ইনপুট: arr[] = {-1,2,5,-3,8,10}

আউটপুট: ২

ব্যাখ্যা: জোড়া: (-1,5) গড় ২, (2,8) গড় ৫ — দুটোই অ্যারেতে আছে।

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

আউটপুট: ৩

ব্যাখ্যা: জোড়া: (1,3) গড় ২, (1,5) গড় ৩, (2,10) গড় ৬।

অ্যালগরিদম (ফ্রিকোয়েন্সি অ্যারে)

1. ফ্রিকোয়েন্সি অ্যারে arr_freq[2001] তৈরি করুন (রেঞ্জ -1000 থেকে 1000)। ইনডেক্স val + 1000-এ ফ্রিকোয়েন্সি রাখুন।
2. প্রতিটি নন-জিরো ফ্রিকোয়েন্সি f জন্য: একই সংখ্যা দিয়ে জোড়া = f*(f-1)/2 (কারণ একই সংখ্যার গড় সেটি আপনাকে) — কাউন্টে যোগ করুন।
3. অল্টারনেট ফ্রিকোয়েন্সি চেক করুন (কারণ কমsekutিভ সংখ্যার গড় ফ্লোটিং পয়েন্ট হয়, অ্যারেতে নেই)।
4. যদি arr_freq[i] এবং arr_freq[j] নন-জিরো এবং arr_freq[(i+j)/2]ও নন-জিরো হয়, তবে arr_freq[i] * arr_freq[j] কাউন্টে যোগ করুন।

C++ বাস্তবায়ন

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

int average_pair(int arr[], int size_1) {
    int count = 0;
    const int N = 1000;
    int size_2 = 2 * N + 1;
    vector arr_freq(size_2, 0);
    
    for (int i = 0; i < size_1; i++) {
        arr_freq[arr[i] + N]++;
    }
    
    for (int i = 0; i < size_2; i++) {
        if (arr_freq[i] > 0) {
            count += arr_freq[i] * (arr_freq[i] - 1) / 2;
            for (int j = i + 2; j < size_2; j += 2) {
                int mid = (i + j) / 2;
                if (arr_freq[j] > 0 && arr_freq[mid] > 0) {
                    count += arr_freq[i] * arr_freq[j];
                }
            }
        }
    }
    return count;
}

int main() {
    int arr[] = {2, 3, 1, 8, 9, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of pairs with average present in the same array are: " 
         << average_pair(arr, size);
    return 0;
}

আউটপুট

Count of pairs with average present in the same array are: 2