এই সমস্যায়, আমাদের একটি arr[] এবং কিছু প্রশ্ন দেওয়া হয়েছে যেগুলি অ্যারেতে L থেকে R-এর মধ্যে রয়েছে। আমাদের কাজ হল L থেকে R.
এর মধ্যে সাবয়ারের XOR প্রিন্ট করাসমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট − অ্যারে ={1, 4, 5, 7, 2, 9} L =1 , R =5
আউটপুট -
ব্যাখ্যা − 4^5^7^2^9
-
এই সমস্যাটি সমাধান করার জন্য, আমরা নিম্নলিখিত পর্যবেক্ষণের উপর ভিত্তি করে একটি অ্যারে তৈরি করব,
-
আমরা একাধিক বিট XOR করব, যদি 1s এর বিজোড় সংখ্যা থাকে, ফলাফল হবে 1 অন্যথায় ফলাফল 0 হবে।
এখন, আমরা একটি দ্বি-মাত্রিক অ্যারে গণনা তৈরি করব যা 1s এর গণনা সংরক্ষণ করবে। মান গণনা [i][j] হল i-j অবস্থানের জন্য 1s সংখ্যার গণনা যা বিটের ith অবস্থানে সাব্যারে অ্যারে[0..j] উপস্থিত 1 এর সংখ্যা। সাব-অ্যারে arr[L..R]-এর সমস্ত বিটের জন্য 1s সংখ্যা গণনা অ্যারে ব্যবহার করে পাওয়া যায়। arr[L...R] =count[i][R] - count[i][L-1] বের করার সূত্র। যদি 1s সংখ্যা বিজোড় হয়, তাহলে ith bit ফলাফলে সেট করা হয়। ith বিটের সাথে সামঞ্জস্যপূর্ণ 2 এর শক্তি যোগ করে চূড়ান্ত ফলাফল পাওয়া যেতে পারে যে এটি বিট সেট করা আছে।
আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void preProcessArray(int arr[], int n, vector<vector<int> >& cnt) {
int i, j;
for (i = 0; i < 32; i++) {
cnt[i][0] = 0;
for (j = 0; j < n; j++) {
if (j > 0) {
cnt[i][j] = cnt[i][j - 1];
}
if (arr[j] & (1 << i))
cnt[i][j]++;
}
}
}
int findXORofSubArray(int L, int R, const vector<vector<int> > count) {
int result = 0;
int noOfOnes;
int i, j;
for (i = 0; i < 32; i++) {
noOfOnes = count[i][R] - ((L > 0) ? count[i][L - 1] : 0);
if (noOfOnes & 1) {
result+=(1 << i);
}
}
return result;
}
int main(){
int arr[] = { 1, 4, 5, 7, 2, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<vector<int> > count(32, vector<int>(n));
preProcessArray(arr, n, count);
int L = 1;
int R = 5;
cout<<"The XOR of SubArray: "<<findXORofSubArray(L, R, count);
return 0;
} আউটপুট
The XOR of SubArray: 13
