양의 정수와 일치하는 값을 포함하는 배열 arr[ ]이 제공됩니다. 목표는 XOR =match가 있는 요소를 포함하는 rr[]의 하위 집합을 찾는 것입니다.
예를 들어
입력
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입니다. Set 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]도 XOR j를 가집니다. 또한 부분 집합 arr[0 to i−2]가 j^arr[i]로 XOR을 갖는다면 부분 집합 arr[0 to 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 값을 갖는 부분 집합의 개수를 반환합니다.
-
처음에 가장 높은 값 =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로 설정합니다.
-
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 루프의 끝에 특정 XOR 값을 가진 부분 집합의 수로 arr_2[size][match]가 있습니다.
-
결과로 rr_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