ধনাত্মক সংখ্যা ধারণকারী একটি অ্যারে arr[] দেওয়া হয়েছে। লক্ষ্য হল 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 যোগ করব৷ জোড় দৈর্ঘ্যের উপসেটের জন্য আমরা দুটি একই উপাদান আছে কিনা তা পরীক্ষা করব, তাই দুটি মধ্যম উপাদান সহ জোড় দৈর্ঘ্যের উপসেটের জন্য গণনা করুন৷
-
ধনাত্মক সংখ্যার অ্যারে arr[] নিন।
-
ফাংশন median_subset(arr, size) arr নেয় এবং সাবসেটের সংখ্যার গণনা ফেরত দেয় যার মধ্যকার একই সাবসেটেও উপস্থিত থাকে।
-
ফাংশন চেক(int temp) একটি পূর্ণসংখ্যা নেয় এবং i=2 থেকে i<=temp পর্যন্ত লুপ ব্যবহার করে সেই সংখ্যার একটি ফ্যাক্টরিয়াল প্রদান করে।
-
count=count*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 ফেরত দিন।
-
মোট =শক্তি (n, r / 2) নিন। (nr/2)
-
মোট 2 সহ মোট আপডেট করুন % মোড। যেখানে mod=1000000007.
-
যদি r জোড় হয় তাহলে temp (মোট * n) % মোড হিসাবে ফেরত দিন, অন্যথায় মোট ফেরত দিন।
-
median_subset() ফাংশনের ভিতরে, গণনা হিসাবে গণনা নিন =শক্তি(2, আকার −1) যা বিজোড় দৈর্ঘ্যের উপসেটের সংখ্যা।
-
sort(arr, arr + size) ব্যবহার করে array arr[] সাজান।
-
কিছুক্ষণ লুপ ব্যবহার করে আমরা বাম মধ্যম উপাদানের জন্য প্রতিটি উপাদান পরীক্ষা করব যতক্ষণ না তারা সমান হয়।
-
temp_2 =মাপ − 1 − temp ধরুন উপাদানের সংখ্যা হিসাবে ডানদিকের মধ্যম উপাদানের।
-
temp_3 =i ধরুন বামদিকের মধ্যম উপাদানের বাম দিকের উপাদানের সংখ্যা হিসেবে।
-
গণনা =(গণনা + com(temp_3 +temp_2, temp_3)) % mod হিসাবে গণনা করতে নির্বাচিত জোড় দৈর্ঘ্যের উপসেট যোগ করুন।
-
while লুপের শেষে আমাদের গণনা থাকবে।
-
ফলাফল হিসাবে রিটার্ন গণনা।
উদাহরণ
#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
