धनात्मक पूर्णांकों और एक मान मिलान वाली एक सरणी गिरफ्तारी [] को देखते हुए। लक्ष्य एआर के सबसेट को ढूंढना है [] जिसमें ऐसे तत्व होते हैं जिनमें एक्सओआर =मैच होता है।
उदाहरण के लिए
इनपुट
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[][] में अनुक्रमणिका i,j पर मान होंगे जैसे कि arr_2[ i ][ j ] में arr[ 0 से i−1 ] के सबसेट से तत्वों का मान XOR है। प्रारंभिक मान 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 to i−2] में XOR j है तो सबसेट arr[0 to i−1] में भी XOR j है। इसके अलावा अगर सबसेट arr[0 to i−2] में XOR j^arr[i] है तो सबसेट arr[0 to i−1] में XOR j भी j ^ arr[i−1] ^ arr[i−1] है। .परिणाम arr_2[ size ][ match] में मिलेगा।
-
एक पूर्णांक सरणी arr[] लें।
-
चर मिलान को पूर्णांक के रूप में लें।
-
फ़ंक्शन सबसेट_एक्सओआर (इंट एआर [], इंट साइज, इंट मैच) एक इनपुट एरे और उसकी लंबाई लेता है और एक विशेष एक्सओआर मान वाले सबसेट की संख्या की गणना करता है।
-
प्रारंभ में उच्चतम =एआर [0] लें। अब लूप के लिए उपयोग करके पूरे arr[] को पार करें और अधिकतम मान को उच्चतम के रूप में खोजें।
-
गणना अस्थायी =(1 <<(int)(log2(highest) + 1)) - 1 अधिकतम संभव XOR मान के रूप में।
-
XORs स्टोर करने के लिए arr_2[size+1][temp+1] सरणी लें।
-
लूप के लिए 0s का उपयोग करके संपूर्ण arr_2 को प्रारंभ करें।
-
arr_2[0][0] =1 सेट करें।
-
लूप के लिए 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.
-
लूप के लिए दोनों के अंत में हमारे पास एक विशेष XOR मान वाले सबसेट की संख्या के रूप में arr_2[size][match] होगा।
-
परिणाम के रूप में arr_2 [आकार] [मिलान] लौटाएं।
उदाहरण
#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