C++-এ যেসব সাবসেটের মিডিয়ান সেই সাবসেটেই থাকে সেটির সংখ্যা গণনা

একটি অ্যারে arr[] দেওয়া আছে যাতে ধনাত্মক সংখ্যা আছে। লক্ষ্য হলো arr[]-এর এলিমেন্টগুলোর সাবসেটগুলো বের করা যাতে সাবসেটের মানগুলোর মিডিয়ান সেই সেটেই থাকে।

উদাহরণ ১

ইনপুট

arr[] = { 1,2,3 }

আউটপুট

যেসব সাবসেটের মিডিয়ান সেই সাবসেটেই থাকে সেটির সংখ্যা: 4

ব্যাখ্যা

মিডিয়ান সেটেই থাকা সেটগুলো: [1], মিডিয়ান ১ [2], মিডিয়ান ২ [3], মিডিয়ান ৩ [1,2,3], মিডিয়ান ২

উদাহরণ ২

ইনপুট

arr[] = { 4,6,5 }

আউটপুট

যেসব সাবসেটের মিডিয়ান সেই সাবসেটেই থাকে সেটির সংখ্যা: 4

ব্যাখ্যা

মিডিয়ান সেটেই থাকা সেটগুলো: [4], [6], [5], [4,6,5]

প্রয়োগ করা পদ্ধতি

এই পদ্ধতিতে ইভেন এবং অড সাইজড এলিমেন্ট চেক করা হয়। তারপর মিডিয়ান বের করা হয় এই ফ্যাক্টের উপর ভিত্তি করে যে অড সংখ্যক আইটেমের জন্য মিডিয়ান মাঝের এলিমেন্ট হিসেবে সেটেই থাকে। তাই 2n-1 কাউন্টে যোগ করা হয়। ইভেন দৈর্ঘ্যের সাবসেটের জন্য চেক করা হয় যেন দুটি মাঝের এলিমেন্ট সমান থাকে, তাই ইভেন দৈর্ঘ্যের সাবসেটের কাউন্ট করা হয়।

ধনাত্মক সংখ্যার অ্যারে arr[] নিন।
median_subset(arr, size) ফাংশনটি সাবসেটের সংখ্যা রিটার্ন করে।
check(int temp) ফাংশনটি একটি ইন্টিজার নিয়ে for লুপ দিয়ে 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 রিটার্ন করুন।
power(int n, int r) ফাংশনটি n^r রিটার্ন করে।
যদি r ০ হয় তবে উত্তর ১, তাই ১ রিটার্ন করুন।
total = power(n, r / 2) নিন।
total = total^2 % mod আপডেট করুন। যেখানে mod=1000000007।
যদি r জোড় হয় তবে temp = (total * n) % mod রিটার্ন করুন, অন্যথায় total রিটার্ন করুন।
median_subset() ফাংশনের ভিতরে count = power(2, size - 1) নিন যা অড দৈর্ঘ্যের সাবসেটের সংখ্যা।
sort(arr, arr + size) দিয়ে অ্যারে সোর্ট করুন।
while লুপ দিয়ে প্রতিটি এলিমেন্টের জন্য বামপাশের মাঝের এলিমেন্ট চেক করুন যতক্ষণ সমান থাকে।
temp_2 = size - 1 - temp নিন ডানপাশের মাঝের এলিমেন্টের ডানে থাকা এলিমেন্ট সংখ্যা।
temp_3 = i নিন বামপাশের মাঝের এলিমেন্টের বামে থাকা এলিমেন্ট সংখ্যা।
বাছাই করা ইভেন দৈর্ঘ্যের সাবসেট কাউন্টে যোগ করুন: count = (count + 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 << "যেসব সাবসেটের মিডিয়ান সেই সাবসেটেই থাকে সেটির সংখ্যা: " << median_subset(arr, size); 
    return 0; 
}

আউটপুট

উপরোক্ত কোডটি রান করলে নিচের আউটপুটটি আসবে:

যেসব সাবসেটের মিডিয়ান সেই সাবসেটেই থাকে সেটির সংখ্যা: 9