একটি অ্যারে arr[] দেওয়া আছে যেটি পজিটিভ ইন্টিজার ধারণ করে এবং একটি মান match। লক্ষ্য হলো arr[]-এর সেই সাবসেটগুলো খুঁজে বের করা যাতে সেটির এলিমেন্টগুলোর XOR = match হয়।
ইনপুট
arr[] = {4, 2, 8, 10} match=12
আউটপুট
Count of number of subsets having a particular XOR value are: 2
ব্যাখ্যা
XOR ১২ হয় এমন সাবসেটগুলো: [4,8], [4,2,10]
ইনপুট
arr[] = {3,5,2,7} match=5
আউটপুট
Count of number of subsets having a particular XOR value are: 2
ব্যাখ্যা
XOR ৫ হয় এমন সাবসেটগুলো: [5], [2,7]
প্রোগ্রামে ব্যবহৃত পদ্ধতি:
এই পদ্ধতিতে আমরা ডাইনামিক প্রোগ্রামিং সমাধান ব্যবহার করি। অ্যারের arr_2[][] ইনডেক্স i,j-এ এমন ভ্যালু থাকবে যাতে arr_2[i][j] হচ্ছে arr[0 to i-1] এর সাবসেটগুলোর XOR ভ্যালু। ইনিশিয়াল arr_2[0][0] = 1, কারণ খালি সেটের XOR ১। arr_2[i][j] = arr_2[i-1][j] + arr_2[i-1][j ^ arr[i-1]]। ফলাফল arr_2[size][match]-এ পাওয়া যাবে।
- ইন্টিজার অ্যারে
arr[]নেওয়া হয়। - ভেরিয়েবল
matchইন্টিজার হিসেবে। subset_XOR(int arr[], int size, int match)ফাংশন ইনপুট অ্যারে এবং দৈর্ঘ্য নিয়ে নির্দিষ্ট XOR মান বিশিষ্ট সাবসেটের কাউন্ট রিটার্ন করে।- ইনিশিয়ালি
highest = arr[0]। পুরো অ্যারে ট্রভারস করে সর্বোচ্চ মানhighestবের করা হয়। temp = (1 << (int)(log2(highest) + 1)) - 1সর্বোচ্চ সম্ভাব্য XOR মান হিসেবে।match > tempহলে ০ রিটার্ন।arr_2[size+1][temp+1]অ্যারে XOR স্টোর করার জন্য।- পুরো
arr_2০ দিয়ে ইনিশিয়ালাইজ।arr_2[0][0] = 1। - ডাবল ফর লুপ:
i=1থেকেsize,j=0থেকেtemp।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]রিটার্ন।
উদাহরণ
#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
