C++で異なる偶数を持つサブセットをカウントします

正の整数の配列が与えられます。目標は、各サブセットに個別の偶数が含まれるように、配列内の数値のサブセットを見つけることです。同じ要素を持つすべてのセットは1としてカウントされます。[2,4,6]と[6,2,4]は同じセットです。

例を挙げて理解しましょう

入力 − arr [] ={1,3,5,7,8,3,2};

出力 −明確な偶数を持つサブセットの数は− 3

説明 −サブセットは− [2]、[8]、[2,8]

入力 − arr [] ={2,4,6};

出力 −明確な偶数を持つサブセットの数は− 7

説明 −サブセットは− [2]、[4]、[6]、[2,4]、[2,6]、[4,6]、[2,4,6]

以下のプログラムで使用されているアプローチは次のとおりです

配列内のすべての偶数のセットを作成します。これにより、明確な偶数の数が得られます。数式は2 ^{偶数カウント} になります -1

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

• Functionsubset_even（int arr []、int size）は数値の配列を受け取り、異なる偶数のサブセットを返します。

• 初期カウントを0とします。

• 偶数のunordered_setun_setを作成します。

• forループを使用してarr[]をトラバースします。 i=0からi

• arr [i]％2 ==0の場合、それは偶数です。 un_setに挿入します。

• count =un_set.size（）//異なる偶数を取ります。

• count =pow（2、count）-1を更新します。

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

例

#include <bits/stdc++.h>
using namespace std;
int subset_even(int arr[], int size){
   int count = 0;
   unordered_set<int> un_set;
   for(int i=0; i<size; i++){
      if (arr[i] % 2 == 0){
         un_set.insert(arr[i]);
      }
   }
   unordered_set<int>:: iterator i;
   count = un_set.size();
   count = pow(2, count) - 1;
   return count;
}
int main(){
   int arr[] = {10, 4, 21, 3, 5, 7, 6, 8};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of subsets having distinct even numbers are: "<<subset_even(arr, size);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of subsets having distinct even numbers are: 15