Cho một mảng arr [] chứa các số nguyên dương và một giá trị khớp. Mục đích là tìm các tập con của arr [] có chứa các phần tử có XOR =match.
Ví dụ
Đầu vào
arr[] = {4, 2, 8, 10} match=12 Đầu ra
Count of number of subsets having a particular XOR value are: 2
Giải thích
Subsets of arr with XOR of elements as 0 are − [ 4,8 ], [4,2,10]
Đầu vào
arr[] = {3,5,2,7} match=5 Đầu ra
Count of number of subsets having a particular XOR value are− 2
Giải thích
ubsets of arr with XOR of elements as 0 are− [ 5 ], [2,7]
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Trong cách tiếp cận này, chúng tôi sẽ sử dụng một giải pháp lập trình động. Mảng arr_2 [] [] sẽ giữ các giá trị tại chỉ mục i, j sao cho arr_2 [i] [j] có giá trị XOR của các phần tử từ các tập con của arr [0 đến i-1]. Lấy giá trị ban đầu arr_2 [0] [0] là 1, đối với tập rỗng XOR là 1. Đặt arr_2 [i] [j] =arr_2 [i-1] [j] + arr_2 [i-1] [j ^ arr [i − 1]], Nếu tập con arr [0 đến i − 2] có XOR là j thì tập con arr [0 đến i − 1] cũng có XOR j. Ngoài ra nếu tập con arr [0 đến i − 2] có XOR là j ^ arr [i] thì tập con arr [0 đến i − 1] cũng có XOR j là j ^ arr [i − 1] ^ arr [i − 1] . Kết quả sẽ được tìm thấy trong arr_2 [size] [match].
-
Lấy một mảng số nguyên arr [].
-
Lấy đối sánh biến dưới dạng số nguyên.
-
Hàm subset_XOR (int arr [], int size, int match) nhận một mảng đầu vào và độ dài của nó và trả về số lượng các tập hợp con có giá trị XOR cụ thể.
-
Ban đầu lấy cao nhất =arr [0]. Bây giờ, xem qua toàn bộ arr [] bằng vòng lặp for và tìm giá trị lớn nhất là cao nhất.
-
Tính temp =(1 <<(int) (log2 (cao nhất) + 1)) - 1 là giá trị XOR lớn nhất có thể.
-
Lấy mảng arr_2 [size + 1] [temp + 1] để lưu trữ XOR.
-
Khởi tạo toàn bộ arr_2 với các số 0 bằng vòng lặp for.
-
Đặt arr_2 [0] [0] =1.
-
Sử dụng vòng lặp for từ i =0 đến i <=size và j =0 đến j <=size, đặt temp_2 =arr_2 [i − 1] [j ^ arr [i − 1]] và đặt arr_2 [i] [j ] =arr_2 [i − 1] [j] + temp_2.
-
Ở cuối cả hai vòng lặp for, chúng ta sẽ có arr_2 [size] [match] là số lượng tập hợp con có giá trị XOR cụ thể.
-
Kết quả là trả về arr_2 [size] [match].
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of number of subsets having a particular XOR value are − 8