นับสับเซตที่ค่ามัธยฐานอยู่ในเซตเดียวกันด้วย C++

ได้รับอาร์เรย์ arr[] ที่มีจำนวนบวก เป้าหมายคือหาสับเซตของสมาชิกใน arr[] ที่ค่ามัธยฐาน (median) ของสับเซตนั้นอยู่ในสับเซตเดียวกันด้วย

ตัวอย่าง

Input

arr[] = { 1,2,3 }

Output

Count of number of subsets whose median is also present in the same subset are: 4

Explanation

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

Input

arr[] = { 4,6,5 }

Output

Count of number of subsets whose median is also present in the same subset are: 4

Explanation

The sets with their medians in that same set are: [ 4 ], [ 6 ], [ 5 ], [ 4,6,5 ]

วิธีการที่ใช้ในโปรแกรม

วิธีนี้ตรวจสอบขนาดคู่และคี่ของสมาชิก แล้วหาค่ามัธยฐานจากข้อเท็จจริงที่ว่า สำหรับจำนวนสมาชิกคี่ ค่ามัธยฐานจะอยู่ในเซตเดียวกันเป็นสมาชิกกลาง ดังนั้นจะเพิ่ม 2n-1 เข้า count สำหรับสับเซตขนาดคู่ จะตรวจสอบว่ามีสมาชิกซ้ำกันสองตัวกลางหรือไม่ นับสับเซตขนาดคู่ที่มีสมาชิกกลางซ้ำกัน

• รับอาร์เรย์ arr[] ของจำนวนบวก
• ฟังก์ชัน median_subset(arr, size) คืนค่าจำนวนสับเซตที่มัธยฐานอยู่ในเซตเดียวกัน
• ฟังก์ชัน check(int temp) คืนค่า factorial ของตัวเลขนั้นด้วยลูป for
• คำนวณ count = count * i คืนค่า factorial ในท้ายลูป
• ฟังก์ชัน com(int n, int r) คืนค่า combination nCr ใช้ temp = check(r) * check(n-r) และ temp_2 = check(n) / temp
• ฟังก์ชัน power(int n, int r) คืนค่า n^r แบบ modulo
• ใน median_subset() ตั้ง count = power(2, size - 1) (จำนวนสับเซตขนาดคี่)
• เรียงลำดับอาร์เรย์ arr[]
• ใช้ while loop ตรวจสอบสมาชิกซ้ำสำหรับสมาชิกกลางซ้าย
• คำนวณ temp_2 = size - 1 - temp (จำนวนสมาชิกขวาของกลางขวา), temp_3 = i (จำนวนสมาชิกซ้ายของกลางซ้าย)
• เพิ่มสับเซตขนาดคู่ที่เลือกเข้า count: count = (count + com(temp_3 + temp_2, temp_3)) % mod
• คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

#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;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of number of subsets whose median is also present in the same subset are: 9