给定一个包含正整数和值匹配的数组 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.Set arr_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] 的 XOR j .结果会在arr_2[size][match]中找到。
取一个整数数组 arr[]。
将变量匹配作为整数。
函数subset_XOR(int arr[], int size, int match) 接受一个输入数组及其长度,并返回具有特定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<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<<"具有特定 XOR 值的子集数为: "<<subset_XOR(arr, size, match); return 0; }输出结果
如果我们运行上面的代码,它将生成以下输出 -
Count of number of subsets having a particular XOR value are − 8