Cho một mảng arr [] chứa các số dương. Mục đích là tìm tập hợp con các phần tử của arr [] sao cho giá trị trung bình của tập hợp con cũng có trong tập hợp đó.
Ví dụ
Đầu vào
arr[] = { 1,2,3 } Đầu ra
Count of number of subsets whose median is also present in the same subset are: 4
Giải thích
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
Đầu vào
arr[] = { 4,6,5 } Đầu ra
Count of number of subsets whose median is also present in the same subset are: 4
Giải thích
The sets with their medians in that same set are: [ 4 ], [ 6 ], [ 5 ], [ 4,6,5 ],
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Trong cách tiếp cận này, chúng tôi sẽ kiểm tra các phần tử có kích thước chẵn và lẻ. Sau đó, chúng ta có thể tìm trung vị dựa trên thực tế là đối với một số lẻ các mục, trung vị có trong cùng một tập hợp với phần tử ở giữa. Vì vậy, chúng tôi sẽ thêm 2n-1 vào số đếm. Đối với tập hợp con độ dài chẵn, chúng tôi sẽ kiểm tra xem có hai phần tử giống nhau hay không, vì vậy hãy đếm các tập hợp con độ dài chẵn có hai phần tử ở giữa.
-
Lấy mảng arr [] của các số dương.
-
Hàm median_subset (arr, size) nhận arr và trả về số lượng các tập con có giá trị trung bình cũng có trong cùng một tập con.
-
Kiểm tra hàm (int temp) nhận một số nguyên và trả về giai thừa của số đó bằng cách sử dụng vòng lặp for từ i =2 đến i <=temp.
-
Tính count =count * i và trả về ở cuối vòng lặp dưới dạng giai thừa.
-
Hàm com (int n, int r) nhận n và r và trả về giá trị của tổ hợp nCr. Bên trong này, take temp =check (r) * check (n - r) và temp_2 =check (n) / temp. Trả về tem_2 dưới dạng giá trị được tính toán.
-
Hàm power (int n, int r) nhận n và r và trả về giá trị nr.
-
Nếu r là 0 thì câu trả lời sẽ là 1 nên trả về 1.
-
Lấy tổng =lũy thừa (n, r / 2). (nr / 2)
-
Cập nhật tổng số với tổng số 2 % mod. Trong đó mod =1000000007.
-
Nếu r là số chẵn thì trả về nhiệt độ là (total * n)% mod, nếu không trả về tổng số.
-
Bên trong hàm median_subset (), lấy count =power (2, size - 1) là số lượng các tập con có độ dài lẻ.
-
Sắp xếp mảng arr [] bằng cách sử dụng sắp xếp (arr, arr + size).
-
Sử dụng vòng lặp while, chúng tôi sẽ kiểm tra từng phần tử cho phần tử ở giữa ngoài cùng bên trái cho đến khi chúng bằng nhau.
-
Lấy temp_2 =size - 1 - temp là số phần tử ở bên phải của phần tử ở giữa cao nhất.
-
Lấy temp_3 =i là số phần tử ở bên trái của phần tử ở giữa ngoài cùng bên trái.
-
Thêm các tập hợp con có độ dài chẵn đã chọn để tính là count =(count + com (temp_3 + temp_2, temp_3))% mod.
-
Vào cuối vòng lặp while, chúng ta sẽ có số đếm.
-
Kết quả là số lượt trả lại.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of number of subsets whose median is also present in the same subset are: 9