सरणी में औसत भी सरणी में मौजूद होने वाले जोड़ों की गणना - C++

समस्या विवरण

हमें एक पूर्णांक सरणी दी गई है जहाँ प्रत्येक तत्व [-1000, 1000] रेंज में है। लक्ष्य उन जोड़ों की गणना करना है जिनका औसत भी सरणी में मौजूद हो।

उदाहरण

इनपुट: arr[] = {-1,2,5,-3,8,10}

आउटपुट: 2

व्याख्या: (-1,5) औसत=2, (2,8) औसत=5

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

आउटपुट: 3

व्याख्या: (1,3)→2, (1,5)→3, (2,10)→6

दृष्टिकोण

आवृत्ति ऐरे का उपयोग करें (आकार 2001, ऑफसेट 1000 ऋणात्मक संख्याओं के लिए)। प्रत्येक शून्येतर आवृत्ति f के लिए:

1. f*(f-1)/2 जोड़ें (समान संख्याओं का औसत वही संख्या होती है)
2. हर दूसरी शून्येतर आवृत्ति j के लिए जाँचें कि क्या (i+j)/2 की आवृत्ति > 0 है। यदि हाँ, तो freq[i]*freq[j] जोड़ें

एल्गोरिदम

1. N=1000, आवृत्ति ऐरे आकार 2*N+1
2. सरणी से आवृत्ति ऐरे भरें: freq[arr[i]+N]++
3. प्रत्येक इंडेक्स i के लिए जहाँ freq[i]>0:
   • count += freq[i]*(freq[i]-1)/2
   • j = i+2 से 2000 तक स्टेप 2:
     • यदि freq[j]>0 && freq[(i+j)/2]>0 तो count += freq[i]*freq[j]
   • count लौटाएँ

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

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

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

int main() {
    int arr[] = {2, 3, 1, 8, 9, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << average_pair(arr, size);
    return 0;
}

आउटपुट

Count: 2