ধনাত্মক পূর্ণসংখ্যা এবং একটি মান মিল ধারণকারী একটি অ্যারে arr[ ] দেওয়া হয়েছে। লক্ষ্য হল arr[] এর উপসেটগুলি খুঁজে বের করা যাতে XOR =মিল আছে এমন উপাদান রয়েছে।
উদাহরণস্বরূপ
ইনপুট
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 থেকে i−2]-এ j হিসাবে XOR থাকলে সাবসেট arr[0 থেকে i−1]-এও XOR j থাকে। এছাড়াও যদি সাবসেট arr[0 থেকে i−2]-এ XOR থাকে j^arr[i], তাহলে সাবসেট arr[0 থেকে i−1]-এও j^arr[i−1] ^ arr[i−1] হিসাবে XOR j থাকে। ফলাফল পাওয়া যাবে arr_2[ আকার ][ ম্যাচ ]।
-
একটি পূর্ণসংখ্যা অ্যারে অ্যার[] নিন।
-
পরিবর্তনশীল মিলকে পূর্ণসংখ্যা হিসাবে নিন।
-
ফাংশন subset_XOR(int arr[], int size, int match) একটি ইনপুট অ্যারে এবং এর দৈর্ঘ্য নেয় এবং একটি নির্দিষ্ট XOR মান সহ উপসেটের সংখ্যার একটি গণনা প্রদান করে৷
-
প্রাথমিকভাবে সর্বোচ্চ =arr[0] নিন। এখন লুপ ব্যবহার করে পুরো arr[] অতিক্রম করুন এবং সর্বোচ্চ হিসাবে সর্বোচ্চ মান খুঁজুন।
-
কম্পিউট temp =(1 <<(int)(log2(সর্বোচ্চ) + 1) ) −1 সর্বাধিক সম্ভাব্য XOR মান হিসাবে।
-
XORs সঞ্চয় করতে array_2[size+1][temp+1] নিন।
-
লুপ ব্যবহার করে পুরো arr_2 0s দিয়ে শুরু করুন।
-
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[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
