นับจำนวนชุดย่อยที่มีค่ามัธยฐานอยู่ในชุดย่อยเดียวกันใน C++

กำหนดอาร์เรย์ 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) ใช้จำนวนเต็มและคืนค่าแฟกทอเรียลของตัวเลขนั้นโดยใช้ for loop จาก i=2 ถึง i<=temp.

• คำนวณ count=count*i แล้วคืนค่าที่จุดสิ้นสุดของลูปเป็นแฟกทอเรียล

• ฟังก์ชัน com(int n, int r) รับ n และ r และส่งกลับค่าของการรวม nCr ภายใน take temp =check(r) * check(n - r) and temp_2=check(n) / temp. คืนค่า tem_2 เป็นค่าที่คำนวณได้

• ฟังก์ชัน power(int n, int r) รับ n และ r และส่งคืนค่า nr

• ถ้า r เป็น 0 คำตอบจะเป็น 1 ดังนั้นให้คืนค่า 1

• รับทั้งหมด =กำลัง (n, r / 2) ( nr/2)

• อัพเดทยอดรวม ² % รุ่น โดยที่ mod=1000000007.

• ถ้า r เป็นเลขคู่ ให้คืนค่า temp เป็น (รวม * n) % mod มิฉะนั้นจะคืนค่าทั้งหมด

• ภายในฟังก์ชัน median_subset() ให้นับเป็น count =power(2, size − 1) ซึ่งเป็นจำนวนชุดย่อยที่มีความยาวคี่

• จัดเรียงอาร์เรย์ arr[] โดยใช้ sort(arr, arr + size)

• การใช้ while loop เราจะตรวจสอบแต่ละองค์ประกอบสำหรับองค์ประกอบตรงกลางด้านซ้ายสุดจนกว่าจะเท่ากัน

• ใช้ temp_2 =size − 1 − temp เป็นจำนวนองค์ประกอบทางด้านขวาขององค์ประกอบตรงกลางด้านขวาสุด

• ใช้ temp_3 =i เป็นจำนวนองค์ประกอบทางด้านซ้ายขององค์ประกอบตรงกลางด้านซ้ายสุด

• เพิ่มชุดย่อยของความยาวคู่ที่เลือกเพื่อนับเป็น count =(count + com(temp_3 +temp_2, temp_3)) % mod.

• ในตอนท้ายของ while loop เราจะนับ

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

#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