计算 C++ 中具有特定 XOR 值的子集数

2023-06-21 12:59:03 69

给定一个包含正整数和值匹配的数组arr[]。目标是找到包含XOR=match元素的arr[]子集。

例如

输入

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

输出结果

具有特定XOR值的子集数为： 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[][]将包含索引i,j处的值，使得arr_2[i][j]具有来自arr[0到i−1]子集的元素的值XOR。取初始值arr_2[0][0]为1，对于空集XOR为1.Setarr_2[i][j]=arr_2[i−1][j]+arr_2[i−1][j^arr[i-1]]，如果子集arr[0到i-2]与j有异或，那么子集arr[0到i-1]也有异或j。此外，如果子集arr[0到i−2]具有作为j^arr[i]的XOR，那么子集arr[0到i−1]也具有作为j^arr[i−1]^arr[i−1]的XORj.结果会在arr_2[size][match]中找到。

取一个整数数组arr[]。

将变量匹配作为整数。

函数subset_XOR(intarr[],intsize,intmatch)接受一个输入数组及其长度，并返回具有特定XOR值的子集数量的计数。

最初取highest=arr[0]。现在使用for循环遍历整个arr[]并找到最大值作为最高值。

计算temp=(1<<(int)(log2(highest)+1))−1作为最大可能的XOR值。

使用数组arr_2[size+1][temp+1]来存储XOR。

使用for循环用0初始化整个arr_2。

设置arr_2[0][0]=1。

使用for循环从i=0到i<=size，以及j=0到j<=size，设置temp_2=arr_2[i−1][j^arr[i−1]]并设置arr_2[i][j]=arr_2[i−1][j]+temp_2。

在两个for循环结束时，我们将arr_2[size][match]作为具有特定XOR值的子集数量的计数。

返回arr_2[size][match]作为结果。

示例

#include
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<<"具有特定XOR值的子集数为： "<输出结果
如果我们运行上面的代码，它将生成以下输出-
Count of number of subsets having a particular XOR value are − 8

计算 C++ 中具有特定 XOR 值的子集数

输入

解释

输入

解释

示例

热门推荐

随机推荐