中央値が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を追加します。偶数の長さのサブセットの場合、2つの同じ要素があるかどうかを確認するため、2つの中間要素を持つ偶数の長さのサブセットをカウントします。

• 正の数の配列arr[]を取ります。

• 関数median_subset（arr、size）は、arrを受け取り、中央値が同じサブセットにも存在するサブセットの数のカウントを返します。

• 関数check（int temp）は整数を取り、i=2からi<=tempまでのforループを使用してその数値の階乗を返します。

• 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を返します。

• total =power（n、r / 2）を取ります。 （nr / 2）

• totalをtotal ² で更新します ％ モッド。ここで、mod=1000000007。

• rが偶数の場合は、tempを（total * n）％modとして返します。それ以外の場合は、totalを返します。

• 関数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ループの最後に、カウントがあります。

• 結果としてカウントを返します。

例

#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