एक सरणी गिरफ्तारी [] जिसमें सकारात्मक संख्याएं हैं। लक्ष्य arr[] के तत्वों के उपसमुच्चय को खोजना है जिससे कि उपसमुच्चय के मानों का माध्यक भी उस समुच्चय में मौजूद हो।
उदाहरण के लिए
इनपुट
arr[] = { 1,2,3 } आउटपुट
Count of number of subsets whose median is also present in the same subset are: 4
स्पष्टीकरण
The sets with their medians in that same set are: [ 1 ], median is 1 [ 2 ], median is 2 [ 3 ], median is 3 [ 1,2,3 ], median is 2
इनपुट
arr[] = { 4,6,5 } आउटपुट
Count of number of subsets whose median is also present in the same subset are: 4
स्पष्टीकरण
The sets with their medians in that same set are: [ 4 ], [ 6 ], [ 5 ], [ 4,6,5 ],
नीचे दिए गए कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
इस दृष्टिकोण में हम सम और विषम आकार के तत्वों की जाँच करेंगे। तब हम इस तथ्य के आधार पर माध्यिका ज्ञात कर सकते हैं कि विषम संख्या में मदों के लिए माध्यिका उसी समुच्चय में मौजूद होती है जिसमें मध्य तत्व होता है। इसलिए हम गिनती में 2n-1 जोड़ देंगे। सम लंबाई के सबसेट के लिए हम जांच करेंगे कि क्या दो समान तत्व हैं, इसलिए दो मध्य तत्वों के साथ सम लंबाई वाले सबसेट की गणना करें।
-
धनात्मक संख्याओं की सरणी गिरफ्तारी [] लें।
-
फ़ंक्शन माध्यक_सबसेट (गिरफ्तारी, आकार) गिरफ्तारी लेता है और उन उपसमुच्चय की संख्या की गणना करता है जिनकी माध्यिका भी एक ही उपसमुच्चय में मौजूद होती है।
-
फंक्शन चेक (इंट टेम्प) एक पूर्णांक लेता है और लूप के लिए i=2 से i<=temp का उपयोग करके उस संख्या का एक फैक्टोरियल देता है।
-
गिनती =गिनती * i की गणना करें, और इसे लूप के अंत में फैक्टोरियल के रूप में वापस कर दें।
-
फ़ंक्शन com(int n, int r) n और r लेता है और संयोजन nCr का मान देता है। इसके अंदर temp =check(r) * check(n - r) और temp_2=check(n) / temp लें। tem_2 को परिकलित मान के रूप में लौटाएं।
-
फ़ंक्शन पावर (int n, int r) n और r लेता है और nr का मान देता है।
-
अगर r 0 है तो उत्तर 1 होगा इसलिए 1 लौटाएं।
-
कुल लें =शक्ति (एन, आर / 2)। (एनआर/2)
-
टोटल के साथ अपडेट करें 2 % मोड। जहां mod=100000007.
-
यदि r सम है तो (कुल * n)% मॉड के रूप में अस्थायी लौटाएं, अन्यथा कुल लौटाएं।
-
फ़ंक्शन के अंदर median_subset(), गिनती को गिनती =शक्ति(2, आकार -1) के रूप में लें, जो विषम लंबाई के सबसेट की संख्या है।
-
सॉर्ट सरणी गिरफ्तारी [] सॉर्ट (गिरफ्तारी, गिरफ्तारी + आकार) का उपयोग कर।
-
थोड़ी देर के लूप का उपयोग करके हम प्रत्येक तत्व के लिए सबसे बाएं मध्य तत्व की जांच करेंगे जब तक कि वे बराबर न हों।
-
सबसे मध्यम तत्व के दाईं ओर मौजूद तत्वों की संख्या के रूप में temp_2 =size − 1 - temp लें।
-
सबसे बाएं मध्य तत्व के बाईं ओर मौजूद तत्वों की संख्या के रूप में temp_3 =i लें।
-
गिनती =(गिनती + कॉम (temp_3 + temp_2, temp_3))% मॉड के रूप में गिनने के लिए चयनित सम लंबाई उपसमुच्चय जोड़ें।
-
जबकि लूप के अंत में हमारे पास गिनती होगी।
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण
#include <algorithm>
#include <iostream>
using namespace std;
#define mod 1000000007;
int check(int temp){
int count = 1;
for (int i = 2; i <= temp; i++){
count = count * i;
}
return count;
}
int com(int n, int r){
int temp = check(r) * check(n − r);
int temp_2 = check(n) / temp;
return temp_2;
}
int power(int n, int r){
if (r == 0){
return 1;
}
int total = power(n, r / 2);
total = (total * total) % mod;
if (r % 2){
int temp = (total * n) % mod;
return temp;
} else {
return total;
}
}
int median_subset(int* arr, int size){
int count = power(2, size − 1);
sort(arr, arr + size);
for (int i = 0; i < size; ++i){
int temp = i + 1;
while (temp < size && arr[temp] == arr[i]){
int temp_2 = size − 1 − temp;
int temp_3 = i;
count = (count + com(temp_3 + temp_2, temp_3)) % mod;
temp++;
}
}
return count;
}
int main(){
int arr[] = { 4, 5, 4, 6 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of number of subsets whose median is also present in the same subset are: "<<median_subset(arr, size);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of number of subsets whose median is also present in the same subset are: 9