एक सरणी arr[] दी गई है जिसमें धनात्मक पूर्णांक हैं और एक मान match है। लक्ष्य arr[] के उन सबसेट को ढूंढना है जिनमें ऐसे एलिमेंट्स हैं जिनका XOR = match है।
उदाहरण के लिए
इनपुट
arr[] = {4, 2, 8, 10} match=12 आउटपुट
Count of number of subsets having a particular XOR value are: 2
व्याख्या
arr के सबसेट जिनके एलिमेंट्स का XOR 0 है - [ 4,8 ], [4,2,10]
इनपुट
arr[] = {3,5,2,7} match=5 आउटपुट
Count of number of subsets having a particular XOR value are- 2
व्याख्या
arr के सबसेट जिनके एलिमेंट्स का XOR 0 है - [ 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 से i-2] का XOR j है तो सबसेट arr[0 से i-1] का XOR भी j है। साथ ही यदि सबसेट arr[0 से i-2] का XOR j^arr[i] है तो सबसेट arr[0 से i-1] का XOR भी j होगा जैसे j ^ arr[i-1] ^ arr[i-1]। परिणाम arr_2[size][match] में मिलेगा।
एक पूर्णांक सरणी arr[] लें।
वेरिएबल match को पूर्णांक के रूप में लें।
फ़ंक्शन subset_XOR(int arr[], int size, int match) एक इनपुट सरणी और इसकी लंबाई लेता है और किसी विशेष XOR मान वाले सबसेट की संख्या की गिनती लौटाता है।
प्रारंभ में highest = arr[0] लें। अब पूरे arr[] को फॉर लूप का उपयोग करके ट्रैवर्स करें और अधिकतम मान को highest के रूप में ढूंढें।
temp = (1 << (int)(log2(highest) + 1)) - 1 की गणना करें अधिकतम संभव XOR मान के रूप में।
XOR स्टोर करने के लिए सरणी arr_2[size+1][temp+1] लें।
फॉर लूप का उपयोग करके पूरे arr_2 को 0 से इनिशियलाइज़ करें।
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 सेट करें।
दोनों फॉर लूप के अंत में हमारे पास 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<<"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
