हमें पूर्णांकों की एक सरणी दी गई है जैसे कि सरणी का प्रत्येक तत्व [- 1000,1000] की सीमा में है। लक्ष्य सरणी के तत्वों के जोड़े को इस तरह से खोजना है कि उनका औसत भी उस सरणी में मौजूद हो। यदि सरणी गिरफ्तार है [] =[1,2,3,4]। तब जोड़े (1,3) और (2,4) होंगे क्योंकि 1,3 का औसत 2 है और 2,4 का औसत 3 है और 2 और 3 दोनों सरणी में मौजूद हैं। गिनती 2 होगी।
आइए उदाहरणों से समझते हैं।
इनपुट - गिरफ्तारी [] ={ -1,2,5,-3,8,10 }
आउटपुट − समान सरणी में मौजूद औसत वाले जोड़े की संख्या है − 2
स्पष्टीकरण − जोड़े ऐसे हैं कि उनका औसत arr[] में मौजूद है - (-1,5) औसत 2 है, (2,8) औसत 5 है। गणना=2
इनपुट - एआर [] ={1,3,2,5,10,6}
आउटपुट − एक ही सरणी में मौजूद औसत के साथ जोड़े की संख्या है − 3
स्पष्टीकरण − जोड़े ऐसे हैं कि उनका औसत arr[] में मौजूद है - (1,3) औसत 2 है, (1,5) औसत 3 है, (2,10) औसत 6 है। गणना =3।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
हम पहले सरणी के सभी तत्वों के लिए एक आवृत्ति सरणी बनाएंगे। फ़्रीक्वेंसी सरणी का आकार मूल सरणी के आकार से दोगुना है क्योंकि इसमें नकारात्मक तत्व भी हो सकते हैं।
ऋणात्मक संख्याओं की आवृत्ति सूचकांक 0 से सूचकांक 1000 तक शुरू होगी। और सकारात्मक संख्याओं की आवृत्ति सूचकांक 1000 से 2000 तक शुरू होगी।
प्रत्येक गैर-शून्य आवृत्ति के लिए ऐसा करें -
-
गिनने के लिए (freq[i]) * (freq[i]-1)/2 जोड़ें, क्योंकि दो समान संख्याओं का औसत ही संख्या है। यदि सरणी में 5 2 हैं। तब कुल जोड़े होंगे (5*(5-1))/2=10.
-
यदि उपरोक्त freq[i] शून्य नहीं है तो वैकल्पिक आवृत्तियों के लिए ट्रैवर्स करना शुरू करें क्योंकि लगातार संख्याओं का औसत होता है जो फ्लोटिंग-पॉइंट होता है और सरणी में नहीं होगा।
-
अगर freq[j] पाया जाता है जो गैर-शून्य है और freq[ (i+j)/2 ] भी शून्य नहीं है। फिर गिनती में freq[i]*freq[j] जोड़ें (क्योंकि प्रत्येक संख्या हर दूसरे नंबर के साथ जोड़ी जा सकती है)।
-
एक पूर्णांक सरणी एआर लें []
-
फ़ंक्शन औसत_पेयर (एआर, आकार) सरणी और उसका आकार लेता है और जोड़े की गिनती देता है जैसे कि जोड़ी में तत्वों का औसत भी सरणी में मौजूद होता है एआर []।
-
आरंभिक गणना को 0 के रूप में लें और N=1000 को प्रारंभ करें।
-
आवृत्ति सरणी की लंबाई की गणना size_2=2*N+1 (श्रेणी के लिए [-1000 से 1000]
. के रूप में करें -
प्रारंभ में फ़्रीक्वेंसी सरणी को 0 से प्रारंभ करें।
-
फ़्रीक्वेंसी एरे को इस तरह से पॉप्युलेट करें कि नकारात्मक तत्वों की आवृत्ति 0 से 1000 तक हो और बाद में सकारात्मक तत्व हों। इसके लिए इंडेक्स में एन जोड़ें।
-
प्रत्येक तत्व के लिए arr[i] आवृत्ति सरणी को arr_freq[arr[i] + N]++;
के रूप में अपडेट करें -
अब फ़्रीक्वेंसी ऐरे को i=0 से i
-
प्रत्येक गैर-शून्य आवृत्ति के लिए (freq[i]) * (freq[i]-1)/2 को शर्त 1 के अनुसार गिनने के लिए जोड़ें।
-
अब चूंकि arr_freq[i] शून्य नहीं है, इसलिए प्रत्येक वैकल्पिक आवृत्ति को पार करें।
-
temp_2 को arr_freq[(i + j) / 2] के रूप में परिकलित करें।
-
अब अगर temp_2 गैर-शून्य है और arr_freq[j] गैर-शून्य है तो शर्त 3 पूरी होती है। उत्पाद के साथ अद्यतन गणना (arr_freq[i] * arr_freq[j]);
-
सभी पुनरावृत्तियों के अंत के बाद, गिनती में ऐसे युग्मों की कुल संख्या होगी।
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int average_pair(int arr[], int size_1){
int count = 0;
int N = 1000;
int size_2 = (2 * N) + 1;
int arr_freq[size_2] = { 0 };
for (int i = 0; i < size_1; i++){
int temp = arr[i];
arr_freq[temp + N]++;
}
for (int i = 0; i < size_2; i++){
if (arr_freq[i] > 0){
int check = (arr_freq[i]) * (arr_freq[i] - 1);
count += check / 2;
for (int j = i + 2; j < 2001; j += 2){
int temp_2 = arr_freq[(i + j) / 2];
if (arr_freq[j] > 0 && temp_2 > 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