양수를 포함하는 배열 arr[]이 제공됩니다. 목표는 부분 집합 값의 중앙값도 해당 집합에 나타나도록 ar[] 요소의 부분 집합을 찾는 것입니다.
예를 들어
입력
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을 받아서 중앙값이 같은 부분집합에도 존재하는 부분집합의 개수를 반환합니다.
-
함수 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을 취하고 nr의 값을 반환합니다.
-
r이 0이면 답은 1이므로 1을 반환합니다.
-
총계 =거듭제곱(n, r / 2)을 취합니다. ( nr/2)
-
총계 2 로 총계 업데이트 % 모드. 여기서 mod=1000000007.
-
r이 짝수이면 온도를 (total * n) % mod로 반환하고, 그렇지 않으면 합계를 반환합니다.
-
median_subset() 함수 내에서 count =power(2, size − 1)로 간주하여 홀수 길이 부분 집합의 수입니다.
-
sort(arr, arr + size)를 사용하여 배열 arr[]를 정렬합니다.
-
while 루프를 사용하여 가장 왼쪽 중간 요소가 같을 때까지 각 요소를 확인합니다.
-
temp_2 =size − 1 − temp를 가장 오른쪽 중간 요소의 오른쪽에 있는 요소 수로 취합니다.
-
temp_3 =i를 가장 왼쪽 중간 요소의 왼쪽에 있는 요소 수로 취합니다.
-
count =(count + com(temp_3 +temp_2, temp_3)) % mod로 계산하기 위해 선택한 짝수 길이 하위 집합을 추가합니다.
-
while 루프가 끝나면 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;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of number of subsets whose median is also present in the same subset are: 9