C++で特定のXOR値を持つサブセットの数をカウントします

正の整数と値の一致を含む配列arr[]が与えられます。目標は、XOR=matchを持つ要素を含むarr[]のサブセットを見つけることです。

例

入力

arr[] = {4, 2, 8, 10} match=12

出力

Count of number of subsets having a particular XOR value are: 2

説明

Subsets of arr with XOR of elements as 0 are −
[ 4,8 ], [4,2,10]

入力

arr[] = {3,5,2,7} match=5

出力

Count of number of subsets having a particular XOR value are− 2

説明

ubsets of arr with XOR of elements as 0 are−
[ 5 ], [2,7]

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

このアプローチでは、動的計画法ソリューションを使用します。配列arr_2[][]には、arr_2 [i][j]がarr[0からi-1]のサブセットからの要素の値XORを持つように、インデックスi、jに値が含まれます。初期値arr_2[0][0]を1とし、空のセットXORは1とします。セットarr_2 [i] [j] =arr_2 [i-1] [j] + arr_2 [i-1] [j ^ arr [i-1]]、サブセットarr [0からi-2]がjとしてXORを持っている場合、サブセットarr[0からi-1]もXORjを持っています。また、サブセットarr[0からi-2]のXORがj^ arr [i]の場合、サブセットarr[0からi-1]のXORjもj^ arr [i-1] ^arr[i-1]になります。 。結果はarr_2[size][match]にあります。

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

• 変数の一致を整数とします。

• 関数subset_XOR（int arr []、int size、int match）は、入力配列とその長さを受け取り、特定のXOR値を持つサブセットの数のカウントを返します。

• 最初は最高=arr[0]を取ります。次に、forループを使用してarr []全体をトラバースし、最大値を最大値として見つけます。

• temp =（1 <<（int）（log2（highest）+ 1））−1を可能な最大XOR値として計算します。

• 配列arr_2[size+ 1] [temp + 1]を使用して、XORを格納します。

• forループを使用してarr_2全体を0で初期化します。

• arr_2 [0] [0]=1に設定します。

• i=0からi<=size、j=0からj<=sizeまでのforループを使用して、temp_2 =arr_2 [i-1] [j ^ arr [i-1]]を設定し、arr_2[i][jを設定します。 ] =arr_2 [i-1] [j]+temp_2。

• 両方のforループの最後に、特定のXOR値を持つサブセットの数のカウントとしてarr_2[size][match]があります。

• 結果としてarr_2[size][match]を返します。

例

#include<bits/stdc++.h>
using namespace std;
int subset_XOR(int arr[], int size, int match){
   int highest = arr[0];
   for (int i = 1; i < size; i++){
      if(arr[i] > highest){
         highest = arr[i];
      }
   }
   int temp = (1 << (int)(log2(highest) + 1) ) − 1;
   if( match > temp){
      return 0;
   }
   int arr_2[size+1][temp+1];
   for (int i = 0; i<= size; i++){
      for (int j = 0; j<= temp; j++){
         arr_2[i][j] = 0;
      }
   }
   arr_2[0][0] = 1;
   for (int i=1; i<=size; i++){
      for (int j=0; j<=temp; j++){
         int temp_2 = arr_2[i−1][j ^ arr[i−1]];
         arr_2[i][j] = arr_2[i−1][j] + temp_2;
      }
   }
   return arr_2[size][match];
}
int main(){
   int arr[] = {4, 2, 8, 10, 3, 4, 4};
   int match = 2;
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of number of subsets having a particular XOR value are: "<<subset_XOR(arr, size, match);
   return 0;
}

出力

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

Count of number of subsets having a particular XOR value are − 8